[백준] 15663번 - N과 M (9)

 

15663번: N과 M (9)

 

 

 

 

 

문제

 

N개의 자연수 중에서 M개를 고른 수열을 중복 없이 사전 순 기준 증가하는 순서로 출력하시오.

 

 

 

 

 

조건

 

1 <= M <= N <= 8

입력으로 주어지는 자연수는 10,000이하

시간 제한 1초

 

 

 

 

 

풀이 방향

 

N과 M 시리즈 중 9번째 문제이다. 사전순 기준 증가하는 순서로 출력해야 하므로 입력으로 주어진 수열을 오름차순 정렬한 후, 백트래킹으로 완전 탐색하여 입력한 순서대로 출력한다. 처음에 주어진 수열을 오름차순 정렬하고 탐색을 하면 출력되는 부분 수열들은 자연히 오름차순 순서일 것이기 때문에 입력한 순서대로 출력하면 그걸로 충분하다.

방법은 크게 두 가지로 M개를 고른 수열이 이전 수열들을 저장한 Set에 없다면 출력객체 StringBuilder에 저장하거나, 저장한 순서대로 출력할 수 있고 중복도 허용하지 않는 LinkedHashSet을 사용할 수 있겠다. 나는 LinkedHashSet을 사용하여 문제를 해결했다.

 

메모

처음에 중복을 없애면서 오름차순으로 출력하기 위해 단순히 TreeSet에 수열을 저장하였는데 주어진 예제가 맞았음에도 '틀렸습니다'를 받았다. 찾아보니 대부분의 사람들이 해당 문제에 TreeSet을 사용하면 안되는 이유로 제네릭이 String 타입이므로 문자열 기준 오름차순 정렬되기 때문이라고 하는데 사실 이해가 잘 되진 않았다. 문자열 기준이라고 해도 "1 2" 가 "1 3" 보다 앞설 것이고 출력되는 수열의 크기는 모두 M으로 동일할 것이기 때문이다. 

하지만 이미 사전에 주어진 수열을 오름차순 정렬하고 탐색을 진행하였으므로 출력에 사용하는 객체인 StringBuilder에는 당연히 오름차순으로 저장되어 있을 것이기 때문에 TreeSet을 사용하지 않아도 다른 방법으로 해결할 수 있다는 것 정도만 알고 넘어가야겠다.

 

출력은 최근에 접한 람다 표현식을 한 번 사용해봤다.

 

 

 

 

 

 

 

 

전체 코드

import java.util.*;

public class ex15663 {
    
    static int A[], arr[], N;
    static boolean visited[];
    static Set<String> set;
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        int M = sc.nextInt();
        
        visited = new boolean[N];
        arr = new int[M];
        A = new int[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextInt();
        
        Arrays.sort(A);
        
        set = new LinkedHashSet<>();
        
        dfs(0, M);
        
        
        set.forEach(System.out::println);
        
        
        sc.close();
    }
    
    
    static void dfs (int depth, int M) {
        
        if (depth == M) {
            String temp = "";
            for (int num : arr) {
                temp += num + " ";
            }
            set.add(temp);
            return;
        }
        
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = A[i];
                dfs(depth+1, M);
                visited[i] = false;
            }
        }
    }
}