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

실버 II

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

문제

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

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

---

입력

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

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

---

출력

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

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

---

접근방식

중복되는 수열을 제외하기 위해 before변수를 추가하였다.길이가 같은 바로 직전의 마지막 값과 새로 추가되는 값이 같을 때 중복되는 수열이 만들어진다. 4 2
9 7 9 1위의 입력 예시에서 before 변수 여부에 따른 결과값은 아래와 같다.

before변수를 사용하지 않고 출력할 경우	before변수를 사용하고 출력할 경우
1 7          1 9  1 9  7 1  7 9  7 9  9 1  9 7  9 9  9 1  9 7  9 9	1 7  1 9  7 1  7 9  9 1  9 7  9 9

먼저 오름차순으로 정렬되므로 arr가 [1, 7, 9, 9]로 재정렬된다.

 

before변수를 사용하지 않고 출력할 경우에서 세 개의 수열 [1, 7] [1, 9] [1, 9] 에서 설명을 하자면

맨 처음에는 before의 초기값 0과 arr[0]인 1이 다르므로 재귀가 실행된다.

그 다음 다시 before는 0으로 초기화 되고, 새로 추가되는 값 7이 비교된다. 0과 7 둘은 다르므로 [1, 7]은 출력 가능한 수열이 된다.

그 다음, 직전의 마지막 값인 7이 before가 되고, 9가 새로 추가되는 값이 된다. 7과 9 둘은 다르므로 [1, 9]은 출력 가능한 수열이 된다.

그 다음, 직전의 마지막 값인 9가 before가 되고, 9가 새로 추가되는 값이 된다. 9과 9 둘은 같으므로 [1, 9]는 또 출력이 불가능하다.

 

[1, 9] [7, 1] 와 같이 앞자리가 바뀔 때는 이전에 자식 노드를 다 돌았으므로 before의 처음은 1, 새로 추가되는 값은 arr[1]인 7이 된다. 따라서, 둘이 다른 걸 확인하고 재귀가 실행된다.

[9, 9] [9, 1]에서 재귀가 실행되지 않는 이유는 before가 9, arr[3]이 9로 똑같아서 재귀로 넘어가지 않고 종료된다.

---

코드

package 백트래킹;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class SLIVER2_BJ15663 {
    /*
        https://www.acmicpc.net/problem/15663
        N과M(9)
     */

    static StringBuilder sb = new StringBuilder();
    static int[] arr;
    static boolean[] visit;
    static int[] result;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        //N과 M입력
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //변수 설정
        arr = new int[N];
        visit = new boolean[N];
        result = new int[M];

        //N개의 수 입력
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //오름차순 정렬
        Arrays.sort(arr);

        dfs(N, M, 0);

        System.out.print(sb);
    }

    public static void dfs(int n, int m, int depth){

        if(m == depth) {
            for(int var: result)
                sb.append(var + " ");
            sb.append("\n");
        }

        else{
            int before = 0;
            for(int i = 0; i < n; i++){
                if(visit[i] == false){
                    if(before != arr[i]) {
                        visit[i] = true;
                        before = arr[i];
                        result[depth] = arr[i];
                        dfs(n, m, depth + 1);
                        visit[i] = false;
                    }
                }
            }
        }
    }
}

---

NOTE

처음 코드를 짰을 때는 store라는 2차원 배열을 두어 이미 있으면 저장하지 않고, 없으면 저장하여 나중에 store배열을 출력하는 방식으로 짰다. 그러니 시간초과가 나서 아래 코드를 참고하여 수정하였다.

 

참고했던 코드이다.

https://yeoncoding.tistory.com/485

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

제가 이해한게 틀릴 수도 있으니 혹시 틀렸다면 알려주십셔..!