[BOJ] 15663. N과 M (9)

문제 원본 : https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int n, m;
    public static int[] arr, perm;
    public static boolean[] check;
    public static StringBuilder builder = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String s = br.readLine();
        n = Integer.parseInt(s.split(" ")[0]);
        m = Integer.parseInt(s.split(" ")[1]);
        arr = new int[n];
        perm = new int[m];
        check = new boolean[n];

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

        Arrays.sort(arr);

        dfs(0);

        bw.write(builder.toString());

        bw.close();
        br.close();
    }

    public static void dfs(int level) {
        if (level == m) {
            for (int p : perm) {
                builder.append(p).append(" ");
            }
            builder.append("\n");
        } else {
            int last = 0;
            for (int i = 0; i < n; ++i) {
                if (!check[i] && last != arr[i]) {
                    check[i] = true;
                    perm[level] = arr[i];
                    last = arr[i];
                    dfs(level + 1);
                    check[i] = false;
                }
            }
        }
    }
}

• N과 M 시리즈 중 어려운 문제
• 순열 문제에서 중복 수열을 제거하는 조건이 추가되었다.
• 이전 수열의 마지막 항이 똑같으면 중복이기 때문에 제외하면 된다.