자바 - 백준 15663 / N과 M (9)

구현 방법

느린 버전

조건

1. ≤ M ≤ N ≤ 8
2. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수
3. 중복되는 수열을 여러 번 출력하면 안됨
4. 수열은 사전 순으로 증가하는 순서로 출력

구현

• 1번 조건에 의해 순열을 사용해도 N!으로 시간초과 안남.
• 2번 조건에 의해 자료형은 int
• 3번 조건을 만족하기 위해 Set<String> checked을 통해 중복 제거
• 4번 조건을 만족하기 위해 입력값 숫자들을 오름차순으로 정렬한 뒤, 순열을 한다.

속도 개선

• 위 방식은 속도가 느렸습니다.

• 속도가 느린 가장 큰 이유는 “Set<String> checked을 통해 중복 제거” 로직입니다.
• 제거해야 하는 중복은 “뽑힌 순열 기준 같은 자리에 다른 인덱스의 같은 숫자”인 경우 입니다.
  • 예시로 1, 2, 2, 3이 있다고 했을 때,
  • 1 2(1번 인덱스)와 1 2(2번 인덱스)의 중복을 제거해야 합니다.
• 따라서 뽑힐 숫자를 고르는 과정에서 같은 숫자를 이미 뽑은 경우는 제외해주는 방법으로 구현하면 됩니다.
  • 이렇게 하면 “Set<String> checked을 통해 중복 제거” 로직이 필요없습니다.

코드

느린 버전

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

/**
* 백준 15663
* N과 M (9)
* 실버2
* <https://www.acmicpc.net/problem/15663>
*/
public class Boj15663 {

    private static int N;
    private static int M;
    private static int[] nums;
    private static Set checked;

    public static void main(String[] agrs) 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());
        nums = new int[N];
        checked = new HashSet<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++)
            nums[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(nums);

        permutation(new int[M], new boolean[N], 0);

    }

    public static void permutation(int[] result, boolean[] visited, int cnt) {
        if(cnt == M) {
            StringBuilder sb = new StringBuilder();

            for(int i : result)
                sb.append(i).append(" ");

            if(!checked.contains(sb.toString())) {
                checked.add(sb.toString());
                System.out.println(sb);
            }

            return;
        }

        for(int i = 0; i < N; i++) {
            if(visited[i])
                continue;

            result[cnt] = nums[i];
            visited[i] = true;
            permutation(result, visited, cnt + 1);
            visited[i] = false;
        }
    }
}

속도 개선

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

/**
* 백준 15663
* N과 M (9)
* 실버2
* <https://www.acmicpc.net/problem/15663>
*/
public class Boj15663 {

    private static int N;
    private static int M;
    private static int[] nums;

    public static void main(String[] agrs) 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());
        nums = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++)
            nums[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(nums);

        permutation(new int[M], new boolean[N], 0);

    }

    public static void permutation(int[] result, boolean[] visited, int cnt) {
        if(cnt == M) {
            StringBuilder sb = new StringBuilder();

            for(int i : result)
                sb.append(i).append(" ");

            System.out.println(sb);

            return;
        }

        int pre = 10001;
        for(int i = 0; i < N; i++) {
            if(visited[i] || pre == nums[i])
                continue;

            pre = nums[i];
            result[cnt] = nums[i];
            visited[i] = true;
            permutation(result, visited, cnt + 1);
            visited[i] = false;
        }
    }
}