[ 백준 15666번 ] N과 M(12)

1. 문제

15666번: N과 M (12)

 

2. 풀이

N과 M 시리즈의 마지막 문제다. 문제의 핵심 조건은 아래와 같다.

 

• 수열에서 같은 수를 여러번 사용할 수 있음
• 비내림차순으로 출력해야 함

 

비내림차순 자체는 입력받은 수열을 오름차순으로 정렬하면 되서 어렵지 않은 조건이지만, 같은 수를 여러번 사용할 수 있게는 어떻게 처리할 것인가?

 

바로 입력 받은 수열의 중복을 제거하는 것이다! 수열의 중복을 제거하고 단순하게 수열의 요소들을 반복 선택하여 M의 길이로 맞춰주면 되는 것으로 코드를 보면 보다 직관적으로 이해될 것이다.

 

3. 소스코드

public class backtracking_15666_NnM12 {
    static int N, M;
    static StringBuilder sb = 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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int[] arr = lineToSortedDistinctArray(br.readLine());

        backtracking(arr, 0, 0, "");

        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    /**
     * @param arr 중복이 제거되고 오름차순 정렬된 수열
     * @param start 시작 idx
     * @param cnt 현재 수열의 길이
     * @param seq 현재 만들고 있는 부분수열
     */
    static void backtracking(int[] arr, int start, int cnt, String seq) {
        if (cnt == M) {
            sb.append(seq.trim()).append("\n");
            return;
        }

        for (int i = start, n = arr.length; i < n; i++) {
            backtracking(arr, i, cnt + 1, seq + arr[i] + " ");
        }
    }

    // 입력 받은 수열의 중복을 제거하고 오름차순으로 정렬
    static int[] lineToSortedDistinctArray(String line) {
        return Arrays.stream(line.split(" "))
                .mapToInt(Integer::parseInt)
                .distinct()
                .sorted()
                .toArray();
    }

}

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code