백준 15650 N과M (2) JAVA로 문제 풀기

N과 M (2)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

---

정답 소스코드

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

public class Main {
    static int N;
    static int M;
    static StringBuilder sb;

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

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

        recur(0, "",1);

        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 + " " + i, i+1);
            }
        }
    }
}

문제 풀이

이 풀이는 초기화 입력받는 부분과

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

재귀함수를 호출하는 부분

  recur(0, "",1);

재귀 호출이 끝나면 출력하는 부분으로 나뉘어져 있습니다.

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

예를 들어, 4 2를 입력했을 경우 N = 4, M = 2가 되며, 이는 전역변수로 활용됩니다.
N = 4이므로 element = 1,2,3,4 가 됩니다.
M = 2이므로 재귀함수를 두 번 더 호출하도록 합니다.

 public static void recur(int applyNum, String makingStr,int startnum) {
        만약 재귀를 더 부를 필요가 없는 경우(M번 호출을 마친 경우)
        else 재귀를 불러야 하는 경우 (아직 뽑을 수가 남은 경우)
    }

처음엔 재귀를 호출한 횟수(applyNum)이 0이므로 else문으로 들어가서 재귀를 호출합니다.

recur(0, "",0);
        recur(1, " 1",1);  
            recur(2, " 1 2",3); //sb에 문자열"1_2_3\n"추가
            recur(2, " 1 3",4); //sb에 문자열"1_3_4\n"추가

        recur(1, " 2",3);  
            ...
        recur(1, " 3",4);
            ...

여기서는 startnum을 줘서 이전에 넣은 값보다 작은 값은 연산에 넣지 않도록 만들었습니다. 어차피 오름차순으로 출력하고 이미 정렬이 된 상태의 수를 다루는 것이기 때문에 이렇게 사용하면 됩니다.

---

두 번째 풀었을 때

이거는 첫 번째 풀었을 때나 두 번째 풀었을때나 큰 차이가 없다. 첫 번째 풀었을 때도 N과M3 - N과M1 - N과M2 순으로 풀었으니 가장 정돈된게 NM2라 더 그런 것 같기도 하다.

import java.util.Scanner;

public class Main {
    static int N;
    static int M;
    static int[] result;
    static boolean[] isVisited;
    static StringBuilder sb;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        result = new int[M+1];
        isVisited = new boolean[N+1];
        sb = new StringBuilder();

        nextPermitation(0, 0);

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

    }

    static void nextPermitation(int apply, int before) {
        if(apply == M) {
            for(int i = 0; i < M; i++) {
                sb.append(result[i]+" ");
            }
            sb.append("\n");
        }else {
            for(int i = 1; i <= N; i++) {
                if(!isVisited[i] && before < i) {
                    isVisited[i] = true;
                    result[apply] = i;
                    nextPermitation(apply+1, i);
                    isVisited[i]= false;
                }
            }
        }
    }
}

이전에 나온 케이스를 모두 기억해두기는 어려워서, 순차적으로 간다는 점을 이용하여
1번째 풀이에서는 이전보다 더 큰 값부터 시작하도록 했다.
2번째 풀이에서는 이전 값보다 현재 값이 더 큰지 비교연산을 통해 재귀를 돌리도록 했다.