BOJ_15663 : N과 M (9)

👉 문제링크

15663번: N과 M (9)

 

---

---

🔸 문제 분석 🔸

• N개의 자연수 중 M개를 고른 수열을 모두 구한다.
  • 수열은 중복되선 안되며 사전 순으로 증가하는 순서로 출력한다.
  • N개의 자연수는 중복이 있을 수 있다.
• 순열로 M개의 원소를 고르고, 중복을 제거하면 된다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    private static int N, M, selected[];
    private static boolean[] checked;
    private static ArrayList<Integer> nums;
    private static ArrayList<String> ans;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        nums = new ArrayList<>();
        selected = new int[M];
        checked = new boolean[N];
        ans = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            nums.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(nums);

        // Permutation
        perm(0);

        // Output
        for (String s : ans) {
            sb.append(s).append('\n');
        }
        sb.deleteCharAt(sb.length() - 1);
        bw.write(sb.toString());
        bw.flush();
    }

    private static void perm(int cnt) {
        if (cnt == M) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < M; i++) {
                sb.append(selected[i]).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);

            if (!ans.contains(sb.toString()))
                ans.add(sb.toString());
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!checked[i]) {
                checked[i] = true;
                selected[cnt] = nums.get(i);
                perm(cnt + 1);
                checked[i] = false;
            }
        }
    }
}

🔸 코드 해석 🔸

• 전형적인 순열 코드에서 중복제거를 위해 ArrayList를 사용했다.
  • 수열이 ArrayList ans에 없다면 추가하고, 있다면 추가하지 않는 방식이다.
• ans의 원소를 줄을 바꿔가며 출력한다.

---

🔸 end 🔸

• 이 문제를 순열이 아닌 조합으로 풀다가 예제 2번에서 잘못됐다는 걸 알아챘다.
• 문제에서 언급한 사전식 정렬을 위해 ans를 ArrayList가 아닌 TreeSet으로 만들었다가 틀렸다.
  
  • 수열을 문자열로 사전식 정렬하면, 원소의 자릿수가 10의 자리 이상이면 오류가 생긴다.
  • 예를 들어 3 2 / 10 10 9 라면, 9 10 / 10 9 / 10 10 이어야 하는데,
    문자열로 정렬하면 10 10 / 10 9 / 9 10 이 나온다.