백준 15651 ] N과M(3) JAVA로 풀기!

N과 M (3)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

출력

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

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

---

답안 소스

소요시간 : 660ms

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);
        N = sc.nextInt();
        M = sc.nextInt();
        sb = new StringBuilder();

        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 ++){
                    recur(applyNum, makingStr + " " + i);
            }
        }
    }
}

이 문제를 풀 때 가장 큰 문제는 시간초과이다.
이 시간초과를 해결하기 위해

1. String 대신 StringBuilder활용
2. System.out.print 대신 BufferedWriter를 사용했다.

해설

가장 쉬운 접근은 for문으로 모든 요소를 돌리며 중복되는 것을 배제하는 것인데, 중첩 for문의 갯수를 가변적으로 사용할 수 없습니다. (for문으로 짜려면 짤 수는 있는데 깊이에 따라 n중 반복문을 유동적으로 작동하도록 짤 수가 없고, 짠다 해도 깊이?가 깊어질수록 코드 작성이 어려워지는 등의 비효율이 발생합니다.) 그러므로 저는 재귀로 완전탐색하기를 사용해보도록 하겠습니다.

Main함수에서는

public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        ...

    }

M과 N을 입력받고

  sb = new StringBuilder();

        recur(0,"");

결과값을 append(이어붙이기)할 StringBuilder를 전역으로 설정한 후, 재귀함수인 recur를 호출했습니다.

       if(applyNum == M){

        }
        else {
            recur(applyNum, makingStr + " " + i);
        }

간단하게, 재귀 함수의 구조는 이렇습니다. 만약 재귀로 부른 횟수가 M개가 아니라면 else문으로 가서 다시 재귀를 호출합니다.

예를 들어 4 2를 입력한다면,
이는 2개를 뽑을 때까지 applyNum(이때까지 뽑은 수)를 호출시마다 1개씩 더해주며, applyNum가 M개(2개)가 되면 더 이상 재귀호출을 하지 않는 방식으로 이루어져 있습니다.
for문으로 1~N까지(4까지) 반복하는데 M번만 재귀를 부를 수 있고, M번 재귀 후 else에서 \n으로 쪼개집니다.

절차를 보다 자세히 살펴보도록 하겠습니다.
recur(0,"");으로 재귀 호출을 하면

 public static void recur(int applyNum = 0 , String makingStr = ""){
        if(applyNum == M){ //applyNum은 0이므로 패스 
           sb.append(makingStr.trim() +"\n"); 
        }
        else {
            ++applyNum; //applyNum이 1이 되고
            for(int i = 1; i <= N ; i ++){
                    recur(applyNum, makingStr + " " + i);  //다시 재귀함수를 호출합니다.
            }
        }
    }

for문이 돌아가면서
recur(1, "" + " " + 1);
recur(1, "" + " " + 2);
recur(1, "" + " " + 3);
recur(1, "" + " " + 4);

가 호출됩니다.

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

그러면 recur(1, " 1");은 applyNum = 1이므로 M = 2와 같지 않아서 else로 가고

  ++applyNum; //applyNum이 2가 되고
            for(int i = 1; i <= N ; i ++){
                    recur(applyNum, " 1" + " " + i); 

를 통해
recur(2, " 1 1");
recur(2, " 1 2");
recur(2, " 1 3");
recur(2, " 1 4");
를 호출합니다.

recur(2, " 1 1");는 applyNum = 2이므로 다음 재귀 호출에서 else문으로 가서

   sb.append(makingStr.trim() +"\n"); //를 통해 

sb에 append연산으로 추가됩니다. 그리고 \n가 붙습니다.

( _1_1이 완성됐지만 맨 앞의 _띄어쓰기를 없애기 위해 trim시켜줍니다.)
그러면 1 1이 됩니다.

---

이런식으로 모든 경우를 탐색할 수 있으며, 재귀로 모든 경우를 탐색한 후엔
main함수로 돌아와서,

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

출력합니다. 이 때 System.out.print보다 효율적인 BufferedWriter를 사용하여 write해주었습니다.

그러면 시간초과가 발생하지 않고 가장 빠르게 문제가 해결됩니다.

---

레퍼런스

https://donggov.tistory.com/53 System.out.println에 대한 고찰

https://code0xff.tistory.com/10 BufferdWriter와 System.out.println 비교

---

두 번째로 풀었을 때

import java.util.Scanner;

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

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

        nextPermitation(0);
        System.out.print(sb.toString());
    }

    static void nextPermitation(int apply) {
        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++) {
                result[apply] = i;
                nextPermitation(apply+1);
            }
        }
    }

}

느낌탓일수도 있지만 이전보다 풀 때 더 이해하기가 쉬워졌네요ㅎㅎ 정올의 주사위던지기도 같은 유형의 문제라 도움됐었던 것 같아요! 내가 원하는 카드를 다 뽑을 때까지만 재귀를 돌리면 됩니다.
예를 들어, 4개의 카드 중 4개를 중복상관없이 뽑는다고 하면
1-1-1-1
1-1-1-2
1-1-1-3
1-1-1-4
1-1-2-1
...
4-4-4-3
4-4-4-4
까지 가는데, 재귀를 사용하면 1-1-1-1 재귀가 다 끝나야만 1-1-1-2 재귀가 실행될 수 있어서 result배열이 혼란스러워지지않고 sb.append까지 가져갈 수 있게 됩니다.