[ps java] BOJ 15663 N과 M (9) 해설

"백트래킹" 대표 시리즈인 N과 M 시리즈 9번 문제 [실버2]

역시 문제 조건 N <= 8 부터가 딱 백트래킹 스멜이 온다!

※ 백트래킹은 재귀를 활용하므로 보통 시간복잡도가 O(N^N), O(N!) 꼴이다

 

풀이의 핵심은 중복을 피하는 것이며, 이에 대해 두 가지 풀이 방법이 있다

1) HashSet 사용 풀이

2) 중복 방지 로직 풀이

 

 

 

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

문제

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

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

입력

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

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

출력

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

예제 입력 1

3 1
4 4 2

예제 출력 1

2
4

예제 입력 2

4 2
9 7 9 1

예제 출력 2

1 7
1 9
7 1
7 9
9 1
9 7
9 9

예제 입력 3

4 4
1 1 1 1

예제 출력 3

1 1 1 1

 

 

 

1) HashSet 사용 풀이

https://claremont.tistory.com/entry/Java-API-Set-%EC%9D%B8%ED%84%B0%ED%8E%98%EC%9D%B4%EC%8A%A4HashSet-LinkedHashSet-TreeSet

[Java API] Set 인터페이스(HashSet, LinkedHashSet, TreeSet)

 

설명은 주석으로 다 해놓았다!

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

// java에서 HashSet에 원소로 배열을 넣으면, 내부적으로 int[].hashCode()와 int[].equals()를 사용하는데
// 배열의 내용이 같아도 객체가 다르면 hashCode()와 equals() 결과가 달라져서 중복 처리가 제대로 안 되거나,
// 하나의 res 배열 객체가 재사용되어도 참조는 동일하므로, 중복 여부 판단이 이상하게 이뤄진다
// 따라서 배열을 문자열(또는 다른 불변 객체)로 바꿔서 HashSet에 저장하거나
// 중복 방지 로직을 재귀(백트래킹) 과정에서 미리 처리해야 한다
public class Main {
    private static int N;
    private static int M;
    private static int[] input;
    private static int[] res;
    private static boolean[] visit;
    private static HashSet<String> set;
    private static StringBuilder sb;

    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());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(input);
        res = new int[M];
        visit = new boolean[N];
        set = new HashSet<>();
        sb = new StringBuilder();
        dfs(0);
        System.out.println(sb);
        br.close();
    }

    private static void dfs(int depth) {
        if (depth == M) {
            if (!set.contains(Arrays.toString(res))) {
                for (int i: res) {
                    sb.append(i + " ");
                }
                sb.append("\n");
                set.add(Arrays.toString(res));
            }
            return;
        }

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

 

 

 

2) 중복 방지 로직 풀이

역시 설명은 주석으로 다 해놓았다!

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

// 중복 방지 로직
// depth마다 for문을 돌 때, 바로 직전 원소와 같은 값이라면(= 중복 숫자)
// 해당 분기를 건너뛰는 식으로 중복 순열을 생성하지 않도록 처리
public class Main {
    private static int N;
    private static int M;
    private static int[] input;
    private static int[] res;
    private static boolean[] visit;
    private static StringBuilder sb;

    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());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(input);
        res = new int[M];
        visit = new boolean[N];
        sb = new StringBuilder();
        dfs(0);
        System.out.println(sb);
        br.close();
    }

    private static void dfs(int depth) {
        if (depth == M) {
            for (int i: res) {
                sb.append(i + " ");
            }
            sb.append("\n");
            return;
        }

        int prevNum = -1;
        for (int i = 0; i < N; i++) {
            if (!visit[i] && input[i] != prevNum) {
                visit[i] = true;
                res[depth] = input[i];
                dfs(depth + 1);
                visit[i] = false;
                prevNum = input[i];
            }
        }
    }
}