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

문제 링크

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

풀이 과정

백트래킹 문제입니다. 백트래킹으로 분류 되어있지만, 유망하지 않은 후보를 제외(가지치기)하는 작업을 하지 않았으므로, 제가 사용한 풀이 방법은 DFS 탐색에 가까운 것 같습니다.

for (int i = 0; i < N; i++)
    arr[i] = sc.nextInt();

Arrays.sort(arr);

수열을 문제에서 정의된 비내림차순 정렬 기준으로 출력해야 합니다. 따라서 먼저 입력받은 N개의 수를 오름차순으로 정렬합니다.

solve(0, 0, "");

정렬이 끝나면, 현재 인덱스와 지금까지 고른 숫자의 개수, 누적될 문자열을 파라미터로 solve 메소드를 호출합니다.

static void solve(int idx, int cnt, String s) {
    if (cnt == M) {
        answer.add(s);
        return;
    }

    for (int i = idx; i < N; i++)
        solve(i, cnt + 1, s + arr[i] + " ");
}

solve 메소드 는 N개의 수 중 M개를 골라 수열을 만드는 작업을 수행합니다.

• 지금까지 진행하면서 고른 숫자 개수가 M개이면, LinkedHashSet 타입의 변수 answer 에 담아, 수열의 중복은 없애고 Set에 들어온 순서는 기억하게 됩니다. 수열은 사전식 오름차순으로 Set 에 입력되는데, 수열이 오름차순 정렬된 배열을 순회하며 생성되기 때문입니다.
• 현재 인덱스 idx 를 기준으로, 다음 번 인덱스의 숫자를 하나 골라 수열을 만들어 봅니다. 맨 처음에 배열은 오름차순으로 정렬되었기 때문에, 수열은 비내림차순을 유지하게 됩니다.

코드

import java.util.*;

public class Main {
    static int N, M;
    static int[] arr;
    static Set<String> answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N];
        answer = new LinkedHashSet<>();

        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();

        Arrays.sort(arr);
        solve(0, 0, "");

        for (String s : answer)
            System.out.println(s);
    }

    static void solve(int idx, int cnt, String s) {
        if (cnt == M) {
            answer.add(s);
            return;
        }

        for (int i = idx; i < N; i++)
            solve(i, cnt + 1, s + arr[i] + " ");
    }
}