[백준] no15657: N과 M (8) - 중복 Combination

문제

* 첫 줄에 N과 M이 주어진다.
* 두 번째 줄에 N개의 숫자가 공백으로 구분되어 주어진다.
* N개의 숫자 중 M개를 뽑는 경우의 수를 중복을 허용하여 구하기

문제 링크 : https://www.acmicpc.net/problem/15657

 

---

원리

재귀 사용

---

풀이방법

Combication 공식을 사용

private static void Combination(int cnt, int k) throws IOException{
    if(cnt == M) {
        for(int i=0 ; i<M ; i++) bw.append(""+subset[i]+" ");
        bw.append("\n");
        return;
    }
    for(int i=k ; i<N ; i++) {
        subset[cnt] = nums[i];
        Combination(cnt+1, i);
    }
}

---

나의 코드

재귀를 이용한 Combination 코드 성능 [ 18132KB, 216ms]

private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int N;
private static int M;
private static int[] nums;
private static int[] subset;

public static void main(String[] args) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    nums = new int[N];
    subset = new int[M];
    StringTokenizer numbers = new StringTokenizer(br.readLine(), " ");
    for(int i=0 ; i<N ; i++) nums[i] = Integer.parseInt(numbers.nextToken());
    Arrays.sort(nums);
    Combination(0,0);

    bw.close();
}
private static void Combination(int cnt, int k) throws IOException{
    if(cnt == M) {
        for(int i=0 ; i<M ; i++) bw.append(""+subset[i]+" ");
        bw.append("\n");
        return;
    }
    for(int i=k ; i<N ; i++) {
        subset[cnt] = nums[i];
        Combination(cnt+1, i);
    }
}

---

Chat GPT 코드

성능 [ 29720KB, 964ms ]

import java.util.*;

public class NonDescendingSequences {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        int m = input.nextInt();

        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = input.nextInt();
        }

        Arrays.sort(nums);
        List<List<Integer>> sequences = findNonDescendingSequences(nums, m);

        for (List<Integer> seq : sequences) {
            for (int i = 0; i < m; i++) {
                System.out.print(seq.get(i) + " ");
            }
            System.out.println();
        }
    }

    private static List<List<Integer>> findNonDescendingSequences(int[] nums, int m) {
        List<List<Integer>> sequences = new ArrayList<>();
        findNonDescendingSequencesHelper(nums, m, new ArrayList<Integer>(), sequences);
        return sequences;
    }

    private static void findNonDescendingSequencesHelper(int[] nums, int m, List<Integer> seq, List<List<Integer>> sequences) {
        if (seq.size() == m) {
            sequences.add(new ArrayList<Integer>(seq));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (seq.isEmpty() || nums[i] >= seq.get(seq.size() - 1)) {
                seq.add(nums[i]);
                findNonDescendingSequencesHelper(nums, m, seq, sequences);
                seq.remove(seq.size() - 1);
            }
        }
    }
}