[백준] Silver 3. N과 M(9)

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

15663번: N과 M (9)

 

방법 1)

• Set을 이용한 풀이

public class Main {

    static int m, n;
    static int [] arr;
    static int [] tmp;
    static boolean[] visited = new boolean[10];
    static StringBuilder sb = new StringBuilder();
    static Set<String> set = new LinkedHashSet<>();
    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());

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

        Arrays.sort(arr);
        recur(0);
        for (String s : set) {
            System.out.println(s);
        }
    }

    private static void recur(int depth) {
        if (depth == m) {
            String res = "";
            for(int i = 0; i < depth; i++){
               res += tmp[i] + " ";
            }
            set.add(res);
            return;
        }

        for(int i = 0; i < n; i++){
            if (!visited[i]){
                visited[i] = true;
                tmp[depth] = arr[i];
                recur(depth + 1);
                visited[i] = false;
            }

        }
    }
}

 

예제 입력이

3 1
4 4 2

인 경우, 출력 값은 중복을 제외하여 2, 4만 출력이 되어야 했다.

 

Set을 사용하면, set에 4가 이미 있는 경우, 더 이상 4를 추가하지 않으므로 유용하게 사용할 수 있다.

 

단, LinkedHashSet을 사용하지 않으면 순서대로 정렬되지 않는다! (Set, Map의 특성상 순서를 보장하지 않는다.)

 

방법 2)

• 이전 값을 저장

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int m, n;
    static int [] arr;
    static int [] tmp;
    static boolean[] visited = new boolean[10];
    static StringBuilder sb = new StringBuilder();
    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());

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

        Arrays.sort(arr);
        recur(0);
        System.out.println(sb.toString());
    }

    private static void recur(int depth) {
        if (depth == m) {
            for(int i = 0; i < depth; i++){
                sb.append(tmp[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        int prev = 0;
        for(int i = 0; i < n; i++){
            if (visited[i]) continue;
            else if (prev != arr[i]) {
                visited[i] = true;
                tmp[depth] = arr[i];
                prev = arr[i];
                recur(depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

 

 

입력 값이 이렇게 있을 떄,

4 2
9 7 9 1

 

arrays를 sort한다면

1 7 9 9

 

이런 형태로 정렬이 될 것 이다.

 

처음부터 흐름을 따라 가면 (1,7)인 경우 depth가 2 이므로 Return. 그리고 (1,9)인 경우에 다시 return을 해준다.

 

그런데, 이제 마지막 9를 체크할 때가 edge case인데, 만약에 이 값을 배열에 넣는다면 (1,9)가 두개가 생겨서 중복이 발생한다.

 

그렇기 때문에, 매번 prev라는 변수를 설정해줘서, 이전 값과 현재 arr[i] 값이 같은지 비교하고, 다른 경우에만 재귀를 진행한다고 보면 된다.

 

 

두가지 방법 모두 알아둬야할 문제다!