Q. 15654 자바 : N과M(5)

Q. 15654 자바 : N과M(5)

 

문제 : boj.kr/15654

실버 3 난이도의 문제이다.

 

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

N개의 자연수는 모두 다른 수이다.

- N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제이다. 

주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다.

 

이 문제는 백트래킹과 재귀함수를 이용해 풀었고, 

이전 계산한 결과를 배열에 저장하고, 깊이가 최대일 때 까지 탐색을 완료하면 저장한 결과를 출력하는 방식으로 풀었다.

 

시간 복잡도를 계산하면, M과 N이 최대 8이므로 

1. 계산 - O(N^M)

2. 출력 - O(NM)

두 계산은 연관이 없으므로 곱해줄 필요는 없으므로 약O(N^M)의 시간복잡도를 가진다.

8^8 = 16,777,216으로 시간초과는 걱정하지 않아도 된다.

자료형은 백트래킹한 수열 저장은 int형 배열에, 중복 여부 확인은 HashSet을 이용했다. 역시 int 범위 내에서 모두 해결할 수 있다.

 

풀이는 아래와 같다.

import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int[] input_val;
    static HashSet<Integer> hashSet;
    static int[] prev_val;

    static void input() {

        N = scan.nextInt();
        M = scan.nextInt();
        hashSet = new HashSet<>();
        input_val = new int[N];
        prev_val = new int[M];
        for (int i = 0; i < N; i++) input_val[i] = scan.nextInt();
    }

    static void pro() {
        Arrays.sort(input_val);
        recur_func(0);
        System.out.println(sb);
    }

    static void recur_func(int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(prev_val[i]).append(' ');
            }
            sb.append('\n');
        }else {
            for (int i = 0; i < N; i++){
                if(hashSet.add(input_val[i])) {
                    prev_val[hashSet.size() - 1] = input_val[i];
                    recur_func(depth + 1);
                    hashSet.remove(input_val[i]);
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}