[BOJ] 15663 - N과 M (9) JAVA

www.acmicpc.net/problem/15663

15663번: N과 M (9)

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

 

1. 입력받은 N개 중 M개의 숫자를 고른 수열

2. 숫자는 여러번 사용될 수 없음. 단, 똑같은 숫자를 여러번 입력받은 경우는 각각을 다른 숫자로 취급

3. 여러번 입력받은 똑같은 숫자를 다른 숫자로 취급하긴 하지만 수열의 같은 자리에 대해서는 같은 숫자로 취급

즉, 중복 수열은 허용하지 않는다.

 

ex ) 

 

입력

4 2

9 7 9 1

 

출력

1 7

1 9

7 1

7 9

9 1

9 7

9 9

 

9를 두 번 입력받기는 했으나 91, 97, 99는 한번씩만 등장

 

중복 수열을 허용하지 않음.

 

 

 

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

비슷한 문제.

 

이 문제는 중복 수열을 허용해서 검사하더라도 해결이 가능하긴 하지만 중복 수열에 대한 검사를 배제하면 시간이 매우 단축됨

 

 

 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static boolean[] check = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if(check[i] == false && used.contains(num[i]) == false) {
                check[i] = true;
                used.add(num[i]);
                permu[deptNow] = num[i];

                dfs(dept, deptNow + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        check = new boolean[n];
        permu = new int[m + 1];
        num = new int[n];

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

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if(check[i] == false && used.contains(num[i]) == false) {
                check[i] = true;
                used.add(num[i]);
                permu[0] = num[i];

                dfs(m, 1);

                check[i] = false;
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

DFS 마다 Set을 통해 중복 수열에 대한 재귀를 배제했다.

해당 수열의 해당 자리에서 이미 사용된 숫자는 다시 오지 못하도록 하여 재귀를 막았다.

 

사실 이 문제에서는 굳이 Set을 사용하지 않고 int 변수 하나만으로도 처리가 가능하다.

 

만들어낸 수열들의 출력 순서를 오름차순으로 해야한다는 조건 때문에 입력받은 N개의 숫자에 대해 미리 정렬을 해놓고 DFS를 돌리기 때문이다.

 

즉, int last를 통해 해당 수열의 해당 자리에서 마지막으로 쓰인 숫자만 기억하고 있다면 중복 수열을 배제할 수 있다.

 

하지만 정렬을 하지 않는 조건일 경우 입력받은 숫자가 1, 0, 1 순서로 되어있다면?

 

해당 수열의 해당 자리에서 1은 맨 처음에 이미 사용 되었지만 0이 사용된 후 last는 0으로 갱신될 것이기 때문에 그 이후에 1이 다시 올 수 있게 되어 중복수열이 발생하게 된다.

 

따라서, 

정렬을 반드시 해야하는 경우 : int 변수 하나로 메모리를 아끼며 해결 가능

정렬을 하지 않는 경우 : Set으로 메모리를 좀 더 써서 해결 가능

 

어차피 이 문제는 주어진 입력의 제한조건이 그리 크지 않았기 때문에 어떤 정렬 여부에 관계없이 어떤 경우라도 해결 가능한 Set을 사용하여 문제를 풀었다.