[백준] 15666번 : N과 M(12) Silver2(실버2) - JAVA[자바]

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

문제 링크

성능 요약

메모리: 19900 KB, 시간: 268 ms

분류

백트래킹

제출 일자

2023년 10월 24일 11:02:20

문제 설명

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

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

입력

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

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

출력

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

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

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static StringBuilder sb = new StringBuilder();
    static int arr[]; // 출력값들이 저장된 arr배열
    static int num[]; // n값이 저장된 배열
    static int n,m;

	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[m];
        num = new int[n];

        for(int i = 0; i < n; i++){
            num[i] = sc.nextInt();
        }
        // 수열은 사전 순으로 증가하는 순서로 출력해야함 그러므로 정렬
        Arrays.sort(num);

        solution(0,0);

        System.out.println(sb.toString());
    }

    // 비내림차순으로 저장되어야한다. 같은 수를 여러 번 골라도 되니까 파라미터는 depth
    private static void solution(int pos, int depth) {
        // depth == m 일 때 배열의 끝까지 간 것임
        if(depth == m){
            for(int num : arr){
                sb.append(num + " ");
            }
            sb.append("\n");
            return;
        }

        // 방금 출력한 값을 뜻하는 before
        int before = -1;
        // 같은 수를 여러 번 골라도 되니까 0부터 시작함
        for(int i = pos; i < n; i++){
            // 방금 배열에 넣은 값인 before와 num[i]가 같다면 continue;
            if(before == num[i]){
                continue;
            }
            // arr인덱스에 현재 값을 넣어준 뒤 recursion
            arr[depth] = before = num[i];
            solution(i,depth+1);
        }
    }
}