백준 15652 ] N과M(4) JAVA로 풀기

N과 M (4)

문제

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

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

입력

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

출력

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

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

답안 소스코드

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

public class Main {
    static int N;
    static int M;
    static StringBuilder sb;
    static Stack<Integer> alreadyIn;

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

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        sb = new StringBuilder();
        alreadyIn = new Stack<>();

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

    public static void recur(int applyNum, String makingStr) {
        if (applyNum == M) {
            sb.append(makingStr.trim() + "\n");
        } else {
            ++applyNum;
            for (int i = 1; i <= N; i++) {
                if (alreadyIn.empty() || i >= alreadyIn.peek() ) {
                    alreadyIn.push(i);
                    recur(applyNum, makingStr + " " + i);
                    alreadyIn.pop();
                }
            }
        }
    }
}

설명

N과M (3)처럼 오름차순으로 완전탐색을 한다. 하지만 지금 답안에 넣으려는 수가 이전보다 더 작은 값일 경우 i >= alreadyIn.peek() 답안에 넣지 않는다. 이는 스택을 활용해서 이전 값과 비교를 통해 구현할 수 있었다.