Recursion: 백준 N과 M(5) - 15654

문제 유형

Recursion

작성 코드

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

public class Main {
    public static StringBuilder answer;
    public static int[] givenNums;
    public static int[] row;
    public static boolean[] checks;
    public static int N;
    public static int M;
    public static void recursive(int depth){
        if (depth == M) {
            for (int element :  row) {
                answer.append(element).append(" ");
            }
            answer.append("\n");
            return;
        }
        for (int i = 0; i < givenNums.length; i++) {
            if (!checks[i]) {
                checks[i] = true;
                row[depth] = givenNums[i];
                recursive(depth+1);
                checks[i] = false;
            }
        }
    }
    public static void input(){
        Scanner scanner = new Scanner(System.in);
        answer = new StringBuilder();
        N = scanner.nextInt();
        M = scanner.nextInt();

        checks = new boolean[N];
        row = new int[M];
        givenNums = new int[N];
        for (int i = 0; i < N; i++) {
            givenNums[i] = scanner.nextInt();
        }
        Arrays.sort(givenNums);
    }
    public static void main(String[] args) {
        input();
        recursive(0);
        System.out.println(answer);
    }
}

접근 방식

1. 주어진 배열의 수열을 구해야 하기 때문에  nPm을 구현할 수 있도록 만들었다. 또한 Arrays.sort를 이용해 정렬을 한다음에 진행했다.
2. Base case의 경우 m의 도달했을 때로 선정하였다.
3. 그 다음으로 현재의 수열에서 재방문을 방지하기 위해 checks라는 배열을 만들었다.
4. 그리고 Base Case에 도달 했을 때 현재의 수열을 반환해야 하기에 row라는 배열을 만들 담았다. (이부분을 생각지 못해서 오랜 시간이 걸렸다.)
5. 마지막으로 m에 도달했을 때 row의 값을 순차적으로 뽑아 Stringbuilder에 담았다.

개선 사항

특별히 어려운 문제는 아니었으나 row를 생각하지 못해 오랜시간이 걸렸다. 문제 속에서 n 과 m의 역할과 결과와의 관계를 미리 인지했더라면 조금더 나았을 수 있었겠다 하는 생각이 들었다.