백준 15663: N과 M (9)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

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

15663번: N과 M (9)

---

N과 M을 9번째 시리즈까지 풀면서, 이번 문제가 가장 어렵게 느껴졌다.
중복 수열을 제거해야 하는 조건이 까다로웠다.

처음에는 입력값을 set으로 받아 중복을 제거해야 하나 싶었는데, 중복 수열인 경우 건너뛰는 방법으로 해결했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static int[] answer;
    static boolean[] isUsed;
    static int n, m;
    static StringBuffer sb;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuffer();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken(" "));
        m = Integer.parseInt(st.nextToken(" "));
        arr = new int[n];
        answer = 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);
        solve(0);
        System.out.println(sb);
    }

    private static void solve(int depth) {

        if (depth == m) {

            for (int i = 0; i < depth   ; i++) {
                sb.append(answer[i] + " ");
            }
            sb.append('\n');
            return;
        }
        int tmp = 0;
        for (int i = 0; i < n; i++) {
            int now = arr[i];

            if(isUsed[i] || tmp == now){
                //이전에 뽑은 값과 현재 뽑은 now와 같다면, 중복된 수열이다.
                continue;
            }else{
                //중복 수열이 아닌 경우
                tmp = now;
                isUsed[i] = true;
                answer[depth] = arr[i];
                solve(depth+1);
                isUsed[i] = false;
            }
        }
    }
}

변수 tmp에는 이번 재귀를 호출하기 직전에 뽑은 값이 담기게 된다. 
따라서 tmp와 지금 막 뽑은 now의 값이 같다면 중복 수열이라는 뜻이므로 continue한다.
예를들어 1, 7, 9, 9로 수가 주어진 경우
맨 처음에 1을 뽑은 뒤 재귀함수를 호출하며

1 7
1 9
1 9

이런 순서로 뽑게 될 것이다. 하지만 두번째로 1 9를 뽑을때, 이미 tmp에는 9가 저장되어 있기 때문에 건너뛸 수 있는 것이다.