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

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

---

[접근 방법]

중복되는 수열을 여러번 출력해서는 안되고, 수열을 사전순으로 증가하는 순서로 출력해야 한다.

 

이전 문제와 다른 점은 "둘째 줄에 주어지는 N개의 수" 가 "중복 가능" 하다는 것 이다.

 

예제 2의 N개의 수를 입력받은 배열인 num = {1, 7, 9 ,9}로 정렬 시킬 수 있다.

기존 방식대로 출력한다면,

1 7

1 9

1 9

7 1

7 9

7 9

9 1

9 7

9 9

9 1

9 7

9 9

로 출력된다.

9가 2개 입력되면서, 출력되는 수열에서 중복이 생기게 되었다.

 

따라서 같은 값을 추가하여도 (중복된 데이터를 넣어도) 무시하는 Set 을 사용하여야 한다.

 

LinkedHashSet<>을 사용하여 문제를 해결하였다.

---

[JAVA 코드]

// 15663번 - N과 M (9)
// 중복 X, 주어진 숫자 (같은 수 O), 같은 수열 X 
import java.util.*;
import java.io.*;

public class Main {

    static int N, M;
    static int[] num; // 자연수 N개 저장
    static int[] arr; // 수열 저장
    static boolean[] visit; // 중복 방지

    // 입력한 순서대로 정렬하는 해시셋
    static LinkedHashSet<String> lhs;
    /*
    set은 인덱스의 개념이 없음.
    set은 같은 값을 넣지 못함. (중복된 데이터를 넣어도 무시됨)
    */

    public static void dfs(int depth){
        if (depth == M){
            StringBuilder sb = new StringBuilder();
            for(int val : arr){
                sb.append(val).append(" ");
            }
            // 완성된 수열을 lhs에 삽입.
            lhs.add(sb.toString());

            return;
        }

        for(int i=0; i<N; i++){
            if (!visit[i]){
                visit[i] = true;
                arr[depth] = num[i];
                dfs(depth + 1);
                visit[i] = false;
            }
        }

        return;
    } // dfs


    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        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());

        num = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        // 1. 변수 초기화 및 dfs 실행
        arr = new int[M]; // 숫자 M개로 이루어진 수열 저장
        visit = new boolean[N];
        lhs = new LinkedHashSet<>();
        Arrays.sort(num);

        dfs(0);

        // 2. 출력
        for(String str : lhs){
            bw.write(str + "\n");
        }
        bw.flush();
        br.close();
        bw.close();      
    }
}

---

[Rewind]

 

1. 어려웠던 점

- 다양한 자료구조를 알지 못하여 해결에 어려움이 있었음.

 

2. 알게된 점

-LinkedHashSet에 대해 알게됨.

 

3. 개선 방향

- 다른 자료구조들에 대한 별도 공부가 필요함.