[백준] 15663. N과 M (9)

문제 링크

[백준] 15663. N과 M (9)

풀이 과정

N개의 수 중 M개를 중복 없이 골라 만든 수열을 사전순으로 출력하는 문제입니다.

boolean[] used = new boolean[N];
Set<String> answer = new LinkedHashSet<>();

중복 없이 골라야 하므로, 중복 체크를 위한 boolean 배열을 선언했습니다. 그리고 만들어진 수열의 중복 제거와 Set 에 추가될 때의 순서를 기억하기 위해 LinkedHashSet 을 사용했습니다.

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

    for (int i = 0; i < N; i++) {
        if (!used[i]) {
            used[i] = true;
            solve(cnt + 1, s + arr[i] + " ");
            used[i] = false;
        }
    }
}

solve 메소드 는 M개의 수를 골라 수열을 만드는 작업을 수행합니다. 방문하지 않은 숫자에 대해 방문 처리를 한 후, solve 메소드를 호출해 수열을 만든 뒤, 돌아와서는 방문 처리를 해제합니다.

코드

import java.util.*;

public class Main {
    static int N, M;
    static int[] arr;
    static boolean[] used;
    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];
        used = new boolean[N];
        answer = new LinkedHashSet<>();

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

        Arrays.sort(arr);

        solve(0, "");

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

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

        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                used[i] = true;
                solve(cnt + 1, s + arr[i] + " ");
                used[i] = false;
            }
        }
    }
}