[문제] 백준 15664번 N과 M(10)

* 출처 www.acmicpc.net/problem/15664

15664번: N과 M (10)

N과 M 시리즈 중 다른 점은 중복되는 숫자가 있어, 수열에서 중복되는 조합은 제거해야 한다는 것이다.

 

내 생각

 

1. 첫번째 풀이

comb함수 내에서 중복된 조합을 제거하기 위해 방금 만든 조합은 StringBuilder를 하나 더 만들어 이에 저장하였다.

그리고 기존의 StringBuilder를 toString()을 사용해 String으로 변환 후 contains 를 통해 앞선 문장과 비교해봤다.

당연히 답은 나오지만, 백준에 제출을 하니 시간 초과가 떴다.

 

2. 두번째 풀이

중복된 것을 제외해야 하니 Set<String>에 넣었다.

public class Main {
	static int N;
	static int M;
	static int[] arr;
	static Set<String> ansSet;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N];
		
		st = new StringTokenizer(in.readLine()," ");
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		ansSet  = new HashSet<String>();
		
		comb(0,new int[M],0);
		System.out.print(sb);
		
	}
	
	static void comb(int toSelect, int[] selected, int startIdx) {
		if(toSelect == M) {
			String tmp = "";
			for(int i=0;i<M;i++) {
				tmp += (selected[i]+" ");
			}
			if(!ansSet.contains(tmp)) {
				ansSet.add(tmp);
				sb.append(tmp);
				sb.append('\n');
			}
			return;
		}
		for(int i=startIdx;i<N;i++) {
			selected[toSelect] = arr[i];
			comb(toSelect+1, selected, i+1);
		}
	}
}