[백준/Java] 15663 - [Silver II] N과 M (9)

문제 링크

문제 설명

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

---

 

 

처음에는 단순히 TreeSet으로 정렬된 수열을 출력하는 방법으로 접근했다

 

하지만 선언했던 TreeSet 구조는 String 타입의 제네릭을 갖고 있기에

 

자연 정렬될 때 다음과 같은 반례가 존재한다

 

현재 상황: String 타입의 숫자를 오름차순 정렬된 상태로 하나씩 출력하고 싶은 상태

 

TreeSet에 110과 19를 add 후 하나씩 출력해보면 ??

TreeSet<String> set = new TreeSet<>();
set.add("19");
set.add("110");
for (String s : set) {
    System.out.println(s);
}

// 출력 결과
// 110
// 19

 

110이 먼저 출력되고 19가 출력되는데 

 

첫 글자 "1" 이 같고

 

두 번째 글자에서 "1" < "9" 비교가 이루어져

 

110이 앞으로 오게 된다

 

이에 따라 접근 방식을 달리하여

 

1. 배열을 오름차순으로 정렬하고
2. 탐색 순서를 보장하는 방법으로 탐색을 진행하여
3. LinkedHashSet에 담아 중복을 제거하는 방식으로 문제 풀이를 진행했다
   • LinkedHashSet은 삽입 순서를 유지하며 중복을 제거한다

해결 답안

import java.util.*;
import java.io.*;

class Main {
    static int N, M;
    static int[] arr;
    static LinkedHashSet<String> set = new LinkedHashSet<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());;
        }
        Arrays.sort(arr); // 배열 정렬

        dfs(0,new int[M]);
        set.forEach(System.out::println);
    }

    static void dfs(int depth, int[] list){
        if(depth == M){ // M개의 숫자를 모두 선택했을 때
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < M; i++) {
                sb.append(list[i]).append(' ');
            }
			
            // 결과를 set에 추가
            set.add(sb.toString());
            return;
        }

        for(int i=0; i<N; i++){
            if(!visited[i]){ // 아직 접근하지 않은 숫자라면
                visited[i] = true; // 방문 표시
                list[depth] = arr[i]; //현재 위치에 숫자 저장
                dfs(depth+1, list); // 다음 깊이로 재귀 호출
                visited[i] = false; // 방문 해제 (백트래킹)
            }
        }
    }
}