[백준_5568번] 카드 놓기

https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

[문제]

 상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

 예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

 n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_5568 {
	static int n,k;
	static int[] card,arr;
	static boolean[] visited;
	static HashSet<String> set=new HashSet<>(); // 중복을 없애기 위해 HashSet 사용
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		card=new int[n];
		visited=new boolean[n];
		arr=new int[n];
		
		for(int i=0;i<n;i++)
			card[i]=sc.nextInt( );
		
		dfs(0);
		System.out.println(set.size()); // HashSet의 크기가 만들 수 있는 정수의 개수
	}
	
	static void dfs(int depth) {
		// k개의 수 선택
		if(depth==k) {
			String str="";
			for(int i=0;i<arr.length;i++)
				str+=arr[i];
			
			// 만들어진 숫자를 HashSet에 삽입, 중복값은 제거된다. 
			set.add(str);
			return;
		}
		
		// 백트래킹을 사용하여 n개의 숫자중 k개 선택
		for(int i=0;i<n;i++) {
			if(visited[i]==false) {
				visited[i]=true;
				arr[depth]=card[i];
				dfs(depth+1);
				visited[i]=false;
			}
		}
	}
}

 

[고찰]

 이번 문제는 완전탐색 문제로 n개의 카드 중 k개를 선택하여 만들 수 있는 모든 정수의 개수를 세면 된다. 이때 입력되는 카드의 값은 중복값도 허용하기 때문에 만들어지는 정수에도 같은 값이 나올 수 있다. 이를 방지하기 위해 HashSet 자료구조를 사용하여 만들어지는 정수의 중복을 없애준다.

 그리고 n개의 카드중 k개를 선택하는 과정에서는 백트래킹 방법을 사용하여 해결할 수 있다. 완전탐색 문제에는 모든 경우의 수를 탐색하는 과정에서 백트래킹과 접목하여 해결할 수 있는 문제가 많은 것 같다.