[문제] 백준 15663번 N과 M (9) - Java

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

15663번: N과 M (9)

 

순열 문제.

이 때, 중복되는 수열을 여러번 출력하지 말아야 하므로 HashSet을 사용했다.

 

처음에 HashSet<StringBuilder> set에 순열이 완성된 수열을 담았는데, 문자열이 중복되서 들어가는 문제가 발생했다.

HashSet에는 String을 담아야 중복되는 문자열을 걸러준다고 한다. 

(참고한 글: https://www.programmersought.com/article/4365667592/ )

 

set에 문자열이 담겨져있지 않으면 새로운 수열이므로 sb에 append 시켜주는 방식으로 코딩했다.

set 개념만 알고 있다면 쉽게 문제 풀 수 있을 것이다.

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);
		//순열
		perm(0, new int[M], new boolean[N]);
        
		System.out.println(sb);
		
	}
	static void perm(int cnt, int[] selected, boolean[] visited) {
		if(cnt == M) {
			StringBuilder temp = new StringBuilder();
			for(int i=0;i<cnt;i++) {
				temp.append(selected[i]).append(' ');
			}
			String str = temp.toString();
			if(!set.contains(str)) {	// set에 들어있는지 확인
				set.add(str);
				sb.append(temp).append('\n');
			}
		
			return;
		}
		for(int i=0;i<N;i++) {
			if(!visited[i]) {
				selected[cnt] = arr[i];
				visited[i] = true;
				perm(cnt+1, selected, visited);
				visited[i] = false;
			}
		}
	}
}