[BOJ] 15663번: N과 M (9) (JAVA)

1. 문제

15663번: N과 M (9)

• N개의 자연수 중에서 M개를 고른 수열
  • 중복X, 순서O => 순열(Permutation)
• 단, 조건) 중복되는 수열을 여러 번 출력하면 안 된다.
  • 중복되는 답을 제거해주어야 한다.

2. 시간복잡도

• 입력
  • 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
  • 순열(Permutation) 알고리즘에서는 O(N! / (N-M)!) 시간복잡도를 가진다.

시간 : O(N! / (N-M)!) = 8! / 0! = 40,320

 

3. 구현

(1) String.contains() 메소드 이용 => 실패

• String.contains() 메소드 이용해서 중복되는 답을 찾았다. => 시간 초과
• 순열 알고리즘을 통해 모든 값을 찾고 중복되는 값을 제거해주었다.

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int M;
    static int[] num;
    static int[] selected;
    static boolean[] visited;
    static Map<Integer, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String str = br.readLine();
        st = new StringTokenizer(str, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        num = new int[N+1];
        visited = new boolean[N+1];
        selected = new int[M+1];
        str = br.readLine();
        st = new StringTokenizer(str, " ");
        for (int i = 1; i <=N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);
        rec_func(1);
        System.out.println(sb);
    }

    static void rec_func(int depth) {
        if(depth == M+1) {
            String str = sb.toString();
            StringBuilder sbr = new StringBuilder();
            for (int i = 1; i <=M; i++) {
                sbr.append(num[selected[i]]).append(" ");
            }
            if(!str.contains(sbr)) {
                sb.append(sbr);
                sb.append("\n");
            }
        } else {
            for (int i = 1; i <=N; i++) {
                if(!visited[i]) {
                    selected[depth] = i;
                    visited[i] = true;
                    rec_func(depth+1);
                    selected[depth] = 0;
                    visited[i] = false;
                }
            }
        }
    }
}

(2) Backtraking 사용

• 정렬 후 탐색할 때 이전 값과 똑같은 경우 아예 탐색하지 않는다.
• ex) N=4,  M=2, 1 7 9 9
  • (    ), lastNum=0
    • (1  ), lastNum=0
      • (1 7), lastNum=7 
      • (1 9), lastNum=9
      • lastNum==9이므로 탐색X
  • (    ), lastNum=1 
    • (7 1), lastNum=1
    • (7 9), lastNum=9
    • lastNum==9이므로 탐색X
  • (     ), lastNum=7
    • (9  ), lastNum=0
      • (9 1), lastNum=1
      • (9 7), lastNum=7
      • (9 9), lastNum=9

public class S2_15663 {
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int M;
    static int[] num;
    static int[] selected;
    static boolean[] visited;
    static Map<Integer, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String str = br.readLine();
        st = new StringTokenizer(str, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        num = new int[N+1];
        visited = new boolean[N+1];
        selected = new int[M+1];
        str = br.readLine();
        st = new StringTokenizer(str, " ");
        for (int i = 1; i <=N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);
        rec_func(1);
        System.out.println(sb);
    }

    static void rec_func(int depth) {
        if(depth == M+1) {
            for (int i = 1; i <=M; i++) {
                sb.append(selected[i]).append(" ");
            }
            sb.append("\n");
        } else {
            int lastNum = 0;
            for (int i = 1; i <=N; i++) {
                if(visited[i]) continue;

                //중복되는 값 제거를 위한 알고리즘
                if(lastNum == num[i]) continue;
                lastNum = num[i];
                
                selected[depth] = num[i];
                visited[i] = true;
                rec_func(depth+1);
                selected[depth] = 0;
                visited[i] = false;
            }
        }
    }
}