백준 15666 N과 M (12)

백준 15666 N과 M (12)

1. 문제 링크

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

15666번: N과 M (12)

 

2. 문제 해결에 대한 아이디어

1. 중복값이 포함된 Input을 배열로 받아 정렬하는 로직이 추가되었다.
2. 문제의 조건대로 정렬을 한 뒤, before 변수를 사용하여 현재 재귀의 for문에서 이전에 선택된 값을 선택하지 않도록 했다.
3. 이후에는 일반적인 중복 조합 로직을 적용하여, visit을 사용하지 않는다.
4. Input에 따라 Output 양이 많아져서, StringBuilder를 사용하여 시간을 줄일 수 있다.

 

3. 코드

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

public class Main {

    static int N, M;
    static int[] nums;
    static int[] candidate;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        N = Integer.parseInt(nm[0]);
        M = Integer.parseInt(nm[1]);

        nums = new int[N];
        visit = new boolean[N];
        candidate = new int[M];

        String[] line = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(line[i]);
        }

        Arrays.sort(nums);

        combination(0, 0);

        System.out.print(sb);
    }

    static void combination(int depth, int start) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(candidate[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        /**
         * nums가 정렬되어있기 때문에 가능한 일이다.
         * nums = {1, 1, 7, 9} 로 정렬되어있다고 가정해본다.
         * for문에서 현재(i) 선택된 값을 before 에 저장 후, 다음 반복에서 접근하는 값(i + 1)과 비교한다.
         * 따라서 0번째 1이 선택되면 1번째 1은 넘어가게 된다.
         * before가 없다면 (1, 7) (1, 9)가 두 번씩 나오게 된다.
         */
        int before = -1;
        for (int i = start; i < N; i++) {
            if (before != nums[i]) {
                candidate[depth] = nums[i];
                before = nums[i];
                combination(depth + 1, i);
            }
        }
    }
}

4. 채점 결과

5. 느낀 점

1. 처음에는 HashSet<Integer []> 에 나오는 모든 배열을 저장하면서, 현재 set에 동일한 배열이 있는지 비교했다.
2. 하지만 이는 시간이 너무 오래 걸렸고, before 변수를 사용해 이전 반복에서 사용한 값을 제외시켰다.
3. Output이 많은 경우, StringBuilder를 적극 활용하자