[백준/Silver II] N과 M (12) - 15666

[Silver II] N과 M (12) - 15666

문제 링크

성능 요약

메모리: 22900 KB, 시간: 216 ms

분류

백트래킹

제출 일자

2024년 12월 7일 03:47:35

문제 설명

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

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

입력

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

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

출력

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

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

 

 

 

 

---

풀이 및 코드

숫자 n개를 입력받고 이를 오름차순으로 정렬한다.

수열은 사전 순으로 증가하는 순서로 출력해야 하므로 오름차순으로 dfs 탐색.

k번째 숫자를 뽑으면 중복을 허용하므로 k, k+1, ... n 번째 숫자 중 하나 뽑는 것을 가정하며 dfs 탐색한다.

여기서 주의해야 할 것은 n개의 숫자 중 중복되는 숫자가 있을 수도 있다는 점이다.

이를 위해 이미 탐색한 수열을 담는 HashSet을 만들었다.

(사실, n개의 숫자를 받을 때 set 에 저장하여 중복되는 숫자를 걸러내면 더 효율이 좋을 것 같다.)

m개의 숫자를 뽑으면 백트래킹한다.

 

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

public class Main {
    private static HashSet<String> check = new HashSet<>(); // 정답을 저장하는 set
    private static StringBuilder answer = new StringBuilder(); // 정답
    private static int[] arr; // 입력받는 수 배열

    private static void backtrack(int idx, int m, String s){
        if(m == 0){ // 백트랙 조건 : 더 이상 뽑을 수 없음
            if(!check.contains(s)){ // 중복되는 순열이면 저장 X
                check.add(s);
                answer.append(s+"\n");
            }
            return;
        }

        // 비내림차순이므로 정렬된 arr를 현재 인덱스부터 차례로 탐색
        for(int i = idx; i < arr.length; i++){
            backtrack(i, m-1,s+arr[i]+" ");
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine().split(" ")[1]);
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        Arrays.sort(arr); // arr를 오름차순으로 정렬
        backtrack(0, m, "");
        System.out.print(answer);
    }
}