[백준] 15663번 : N과 M (9)

문제

 

 

접근 방식

주어진 수들을 정렬하여 오름차순으로 출력하는건 이전 문제들과 똑같지만

이미 뽑은 수를 재사용하면 안되고 중복된 수열은 제외해야 한다는 조건이 붙었다.

 

중복된 수열을 제외하는 부분이 많이 힘들었는데

이미 뽑은 수를 체크하는 배열 외에도

현재 재귀 호출에서 이전에 뽑은 수를 기록해둘 지역변수를 하나 추가해서 해결했다.

 

예를 들어 [1, 7, 9, 9] 같은 수들이 주어진 경우

두 번 등장하는 9를 각각 9a, 9b라고 했을 때

1 7 9a 9b와 1 7 9b 9a는 같은 수열로 취급하여 하나만 출력해야 하는데

이때 9a를 이전에 사용한 값이라고 저장해둘 지역변수에 담아두면

나중에 1 7 까지 뽑고 9b를 뽑는 순간에 비교하여 넘어갈 수 있다.

 

글로 적으려니 설명을 잘 못하겠어서 재귀 호출 순서를 일부만 적어보겠다.

 

[1, 7, 9a, 9b]

size = 0일 때 1을 뽑는다. >> before = 1
	size = 1일 때 7을 뽑는다. >> before = 7
    	size = 2일 때 9a을 뽑는다. >> before = 9a
        	size = 3일 때 9b을 뽑는다. >> before = 9b
        size = 2일 때 9b을 뽑는다. >> 9a == 9b 해당 재귀 호출을 넘어감
    size = 1일 때 9a을 뽑는다. >> 7 != 9a >> before = 9a
    	...

 

주의할 점이 있다면 이전에 사용한 값을 담을 변수는 전역 변수가 아니라

재귀 메서드 내에서 각각의 스택에서 사용될 지역 변수로 선언해야 한다.

 

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;
	private static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n];
		sequence = new int[m];
		isUsed = new boolean[n];

		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0);

		System.out.println(sb);
	}

	private static void createSequence(int size) {
		if (size == m) {
			for (int seq : sequence) {
				sb.append(seq).append(" ");
			}
			sb.append("\n");

			return;
		}

		int before = 0;

		for (int i = 0; i < n; i++) {
			if (!isUsed[i] && before != arr[i]) {
				sequence[size] = arr[i];
				isUsed[i] = true;
				before = arr[i];
				createSequence(size + 1);
				isUsed[i] = false;
			}
		}
	}
}