[Java] 15656 N과 M

문제

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

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

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

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

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

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

 

요약하면 N개의 숫자를 중복가능하게 M개를 뽑아내어 가능한 숫자 조합을 사전 오름차순으로 나열하라는 의미이다.

DFS와 재귀를 활용한 문제이다.

 

문제 풀이

우선 받은 숫자들을 배열에 정렬한뒤 

위 사진 처럼 count를 받는 dfs 메소드가 있고 dfs 메소드는 result[count]에 for문으로 number숫자를 하나 씩 집어넣고 count + 1을 받은 dfs 메소드를 재귀로 실행하면 된다. 

이후 M과 count의 값이 같을 때 result에 들어간 숫자를 " "으로 붙여서 저장한다.

그러면 우선 2로 이루어진 2 2 2 문자열이 완성되고 이 다음으로 count 2에 다음 숫자인 4가 주입되면서 2 2 4가 저장된다.

같은 방법으로 2 2 5까지 완성되고 나면 count1에서 2가 4로 바뀌고 2 4 x로 이루어진 다음 숫자들이 저장된다.

자바 코드

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

public class NM {
    private static int N;
    private static int M;
    private static int[] numbers;
    private static int[] result;
    private static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // N과 M 값 받기
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // N값을 이용한 배열 생성
        numbers = new int[N];
        result = new int[N];

        // N개의 숫자 받아서 numbers 삽입
        String[] line = br.readLine().split(" ");
        for(int i = 0; i < numbers.length; i++)
            numbers[i] = Integer.parseInt(line[i]);

        // 정렬
        Arrays.sort(numbers);

        dfs(0);
        System.out.println(sb);
    }

    private static void dfs(int count) {
        // count가 M개와 같을 경우 현재까지 result에 저장된 숫자들을 " "으로 연결 후 종료
        if (count == M) {
            for (int i = 0; i < M; i++) {
                sb.append(result[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // result에 정렬된 낮은 숫자부터 하나씩 넣고 재귀
        for (int i = 0; i < N; i++) {
            result[count] = numbers[i];
            dfs(count + 1);
        }
    }

}