[조합] BOJ_15664 N과M(10)JAVA

문제

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

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

예제 입력 

4 2
9 7 9 1

예제 출력 

1 7
1 9
7 9
9 9

해결방법

위의 예제 출력을 보면 중복이 가능한 중복조합처럼 보이지만

입력에서 9가 두번 들어갔기 때문에 순서를 상관하지 않고 중복을 허용하지 않는 조합이다. 

 

이때 주의할 점은 9가 2번 들어갔다는 점인데

한번 9가 쓰이면 더이상 쓰이지 않도록 만들어줘야한다.

 

 

해결 코드

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

public class Main {
    //조합
    static int N,M;
    static int[] output;
    static int[] num;
    static BufferedReader br;
    static StringBuilder sb;
    static StringTokenizer st;
    static boolean[] isVisited;

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        num = new int[N];
        output = new int[M];
        isVisited = new boolean[N];

        for(int i=0; i<N;i++){
            num[i] =  Integer.parseInt(st.nextToken());
        }

        Arrays.sort(num);

        comb(0,0);
        System.out.println(sb);

    }

private static void comb(int start, int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) {
            sb.append(output[i]).append(" ");
        }
        sb.append("\n");
        return;
    }

    int before = -1; // 이전에 선택한 값

    for (int i = start; i < N; i++) {
        if (before == num[i]) continue; // 이전 값과 같으면 중복이므로 건너뛰기

        before = num[i];  // 현재 값을 이전 값으로 업데이트
        output[depth] = num[i];
        comb(i + 1, depth + 1);  // 다음 인덱스부터 탐색 (중복 방지)
    }
}
}

 

이해가 잘 안되었던 부분

여기서 before이 필요한 이유!

상황 설명

문제:
입력된 숫자들 중에서 중복 없이 M개의 숫자를 선택하는 조합을 만들어야 함
근데 입력된 숫자들에 중복된 값이 있을 수 있음

---

예제

입력:

N = 4, M = 2 숫자들: [1, 1, 2, 3]

여기서 1이 두 번 나옴. 근데 같은 조합을 두 번 출력하면 안 됌!

before를 썼을 때

before는 같은 깊이에서 같은 값이 나오면 건너뛰도록 도와줌

예)

1. 첫 번째 1 선택 (before = 1)
   • 두 번째로 2 선택 → 1 2 출력
2. 두 번째 1 선택 시
   • "어? 방금 전에 1 골랐잖아!"
   • 그래서 before == now 조건에 걸려서 건너뜀!

결국 중복된 1 2는 한 번만 출력된다.