백준 - 15666번(N과 M(12))

문제 출처: https://www.acmicpc.net/problem/15666

문제

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

  • N개의 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

• 처음 시도

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

public class Main {

    private static Set<String> set = new LinkedHashSet<>(); // 중복 제거 + 순서보장

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder(); // 마지막 출력 저장용
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken()); // N개의 자연수 중
        int M = Integer.parseInt(tokenizer.nextToken()); // M개를 고름
        tokenizer = new StringTokenizer(reader.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(arr); // 사전순 출력 위한 정렬

        combiRepeat(arr, 0, 0, M, new StringBuilder());

        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()) {
            sb.append(iterator.next()).append("\n");
        }

        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }

    private static void combiRepeat(int[] arr, int start, int count, int M, StringBuilder sb) {
        if (count == M) {
            set.add(sb.toString());
            return;
        }

        for (int i = start; i < arr.length; i++) {
            int size = sb.length();
            sb.append(arr[i]).append(" ");
            combiRepeat(arr, i, count + 1, M, sb);
            sb.setLength(size);
        }
    }

}

• 두번째 시도

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

public class Main {

    private static StringBuilder result = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken()); // N개의 자연수 중
        int M = Integer.parseInt(tokenizer.nextToken()); // M개를 고름
        tokenizer = new StringTokenizer(reader.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(arr); // 사전순 출력 위한 정렬

        combiRepeat(arr, 0, 0, M, new StringBuilder());

        System.out.println(result);
    }

    private static void combiRepeat(int[] arr, int start, int count, int M, StringBuilder sb) {
        if (count == M) {
            result.append(sb).append("\n");
            return;
        }

        int temp = 0; // 직전에 처리한 수를 기억하기 위한 변수

        for (int i = start; i < arr.length; i++) {
            if (arr[i] != temp) {
                int size = sb.length();
                sb.append(arr[i]).append(" ");
                combiRepeat(arr, i, count + 1, M, sb);
                sb.setLength(size);
                temp = arr[i];
            }
        }
    }

}

• 절반의 승리라고 할 수 있다.
• 우선 이 문제는 중복조합으로 접근했다. 사전순 출력이므로 Arrays.sort()를 통해 정렬한 다음 진행했다.
• 중복을 제거하기 위해 LinkedSet()을 활용했는데, 처음에 출력 초과가 나와서 구글링을 하던 중, 두 번째 방법을 찾게 되었다.
• 조합의 의미를 다시 한번 되새겼다. 조합의 의미를 가지고 중복을 제거하려면 제일 처음에 나오는 수가 중복되지 않게 하면 된다. 해당 수의 재귀를 다 돌면 그 수로 나오는 경우의 수는 다 뽑은 것이므로, 그 다음에 똑같은 수로 재귀를 돌리면 중복이 발생하게 된다. 이를 막기 위해 직전에 돌린 수를 변수에 저장하고, 현재 차례의 수와 비교한다.
• 번외로, StringBuilder를 처리하는 부분에서 완전 뻘짓했다... 처음에 재귀를 돌고 나서 sb.setLength(sb.length() - 2)로 하여 직전까지로 돌이키는 방식을 처리했으나 계속 출력 초과가 나와서 검토하던 중, 이렇게 하면 한 자리수에서만 유효하다!는 것을 알게 되었다...