백준 15655 ] N과 M(6) JAVA로 풀기

N과 M (6)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

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

출력

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

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

문제 이해

N과 M(2)문제와 완전히 동일합니다. 여기서는 N이 주어져도 N보다 작거나 같은 모든 자연수(1,2,3...N)을 element로 사용하지 않고 입력으로 주어진 element를 사용합니다. 때문에 그만큼의 element = new int[N]; int배열을 만들어 처리했습니다.

문제 소스코드

  import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static int M;
    static StringBuilder sb;
    static int[] element;

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

        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();

        N = sc.nextInt();
        M = sc.nextInt();
        element = new int[N];
        for(int i = 0; i < N; i++){
            element[i] = sc.nextInt();
        }
        Arrays.sort(element);

        recur(0, "",0);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString().trim());
        bw.close();
    }

    public static void recur(int applyNum, String makingStr,int startnum) {
        if (applyNum == M) {
            sb.append(makingStr.trim() + "\n");
        } else {
            ++applyNum;
            for (int i = startnum ; i < N; i++) {
                    recur(applyNum, makingStr + " " + element[i], i+1);
            }
        }
    }
}

해설

여기서도 stack이나 used 등을 따로 두지 않은 이유가 바로 이전에 사용한 값보다 더 큰 값을 사용하는 특징을 갖기 때문입니다. element요소를 입력받아 오름차순으로 정렬한 뒤, 재귀 호출을 해주었습니다. 재귀함수를 호출할 때마다 applyNum이 늘어나며, 이게 M과 같아지는 경우 결과값을 sb StringBuilder에 넣어줍니다. element가 실제 결과값에 들어가며 그 다음부터는 i+1인덱스부터 탐색하게 됩니다. 때문에 element[i]보다 작은 값이 결과에 반영될 여지가 없습니다.