[문제] 백준 15665번 N과 M (11) - Java

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

15665번: N과 M (11)

중복순열 문제다.

앞에서 푼 문제에서 hashset을 사용했던 것 대신 linkedlist를 사용했더니 시간초과가 떴다.

검색해보니, hashset보다 linkedlist의 시간이 훨씬 많이 나온다.

(참고 글: https://12bme.tistory.com/91 - Collection 인터페이스별 성능 비교 글)

public class Main {
	static int N,M;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	static HashSet<String> set = new HashSet<>();
	
	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);
		// 중복순열
		pperm(0, new int[M]);
		
		System.out.println(sb);
		
	}
	static void pperm(int cnt, int[] selected) {
		if(cnt == M) {
			StringBuilder tmp = new StringBuilder();
			for(int i=0;i<cnt;i++) {
				tmp.append(selected[i]).append(' ');
			}
			tmp.append('\n');
			String str = tmp.toString();
			
			if(!set.contains(str)) {
				set.add(str);
				sb.append(tmp);
			}
			
			return;
		}
		for(int i=0;i<N;i++) {
			selected[cnt] = arr[i];
			pperm(cnt+1, selected);
		}
	}
}