[JAVA] 백준 15663

 

 

15663번: N과 M (9)

 

문제

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

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

풀이

이전 문제들(15649, 15650)과 다른점은 해당 문제는 연속된 수열이 아닌 주어진 수열을 가지고 새로운 수열을 만드는 것이다.

이때, 수열에 중복된 수가 있을 수 있다는 것이 어려웠다.

만든 수열을 사전순으로 출력해야 하기 때문에 주어진 수열을 sort 메서드로 먼저 정렬한 후 사용했다.

📌 백트래킹 탐색

    public static void DFS(int depth, String num){
        if(depth == M){
            value.add(num);
            return;
        }

        for(int i=1; i<N; i++){
            if(!V[i]){
                V[i] = true;
                DFS(depth+1, num +" "+ A[i]);
                V[i] = false;
            }
        }
    }

각 수열을 돌면서 모든 수열을 탐색한다.

이때 중복된 수열이 발생할 수 있는데 해당 문제는 나중에 지울 것이다.

📌 중복된 수열 제거 및 출력

       value = (ArrayList<String>) value.stream().distinct().collect(Collectors.toList());
       for(String x : value){
           sb.append(x.substring(1)).append("\n");
       }
       System.out.println(sb);

스트림 API를 이용해서 중복을 제거하고 StringBuilder로 출력하였다.

📌 전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

class Main {
    static int N;
    static int M;
    static int[] A;
    static boolean[] V;
    static StringBuilder sb = new StringBuilder();
    static ArrayList<String> value = new ArrayList<>();
    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())+1;
       M = Integer.parseInt(st.nextToken());
       A = new int[N];
       V = new boolean[N];

       st = new StringTokenizer(br.readLine() , " ");
       for(int i=1; i<N; i++){
           A[i] = Integer.parseInt(st.nextToken());
       }

       Arrays.sort(A);
       DFS(0, "");
       value = (ArrayList<String>) value.stream().distinct().collect(Collectors.toList());
       for(String x : value){
           sb.append(x.substring(1)).append("\n");
       }
       System.out.println(sb);
    }

    public static void DFS(int depth, String num){
        if(depth == M){
            value.add(num);
            return;
        }

        for(int i=1; i<N; i++){
            if(!V[i]){
                V[i] = true;
                DFS(depth+1, num +" "+ A[i]);
                V[i] = false;
            }
        }
    }

}

결과

중복을 체크하는 것이 모든 수열을 탐색한 후 제거하는 방식이였기 때문에 뭔가 비효율적이라고 생각해서 HashSet을 이용해서 중복을 체크하는 방식을 사용해서 문제를 해결해보았지만 더 느렸다.

📌 HashSet 풀이

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

class Main {
    static int N;
    static int M;
    static int[] A;
    static boolean[] V;
    static StringBuilder sb = new StringBuilder();
    static HashSet<String> set = new HashSet<>();
    static int count = 0;
    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())+1;
       M = Integer.parseInt(st.nextToken());
       A = new int[N];
       V = new boolean[N];

       st = new StringTokenizer(br.readLine() , " ");
       for(int i=1; i<N; i++){
           A[i] = Integer.parseInt(st.nextToken());
       }

       Arrays.sort(A);
       DFS(0, "");
       System.out.println(sb);
    }

    public static void DFS(int depth, String num){
        if(set.contains(num)) return;
        if(depth == M){
            set.add(num);
            sb.append(num.substring(1)).append("\n");
            return;
        }

        for(int i=1; i<N; i++){
            if(!V[i]){
                V[i] = true;
                DFS(depth+1, num +" "+ A[i]);
                V[i] = false;
            }
        }
    }

}