백준 15649 ] N과 M(1) JAVA로 풀기

N과 M (1)

이는 N과 M (3)을 풀고 나서 푸는게 더 좋을 것으로 보입니다. (https://onepinetwopine.tistory.com/515)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 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.contains(i)) {
                    alreadyIn.push(i);
                    recur(applyNum, makingStr + " " + i);
                    alreadyIn.pop();
                }
            }
        }
    }
}

---

문제 이해하기

즉 자연수 N이 주어지면 1,2,3,...N까지 요소가 있고, 여기서 M개를 중복되지 않게 뽑는 경우를 모두 출력하면 된다. 예를 들어,
입력이 3 1 인경우
1, 2, 3 을 한 개씩 중복되지 않게 뽑는다. 그래서 답은

1
2
3

이 되고,

입력이 4 2 인 경우
1,2,3,4를 두 개씩 중복되지 않게 뽑는다. 그래서 답은

1 2 
1 3 
1 4
2 1 
2 3
2 4
3 1 
3 2 
3 4
4 1 
4 2 
4 3 

이다.

---

문제 풀기

1. 가장 쉬운 접근은 for문으로 모든 요소를 돌리며 중복되는 것을 배제하는 것인데,
   중첩 for문의 갯수를 가변적으로 사용할 수 없으므로 패스.
   (for문으로 짜려면 짤 수는 있는데 깊이에 따라 n중 반복문을 유동적으로 작동하도록 짤 수가 없고,
   짠다 해도 깊이?가 깊어질수록 코드 작성이 어려워진다.)

2. 재귀로 완전탐색하기

두 번째 접근은 재귀를 사용하여 완전탐색을 하는 것입니다.

재귀로 완전 탐색하기

N = 4 M = 2 인 예시로 한정하여 재귀를 활용한 완전탐색을 해보면

(최종 출력할 답안을 StringBuilder를 활용하여 계속 덧붙여 만들도록 했습니다.)

public class Main {
    static int N = 4;
    static int M = 2;
    static StringBuilder sb;

    public static void main(String[] args) {
        sb = new StringBuilder();

        recur(0,"");
        print(sb.toString().trim());
    }

    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);
                    // i = 1일 때 다시 재귀가 호출되고 이는 다시 1~4를 탐색합니다. 
                    // i = 2일 때 다시 재귀가 호출되고 이는 다시 1~4를 탐색합니다.
                    // i = 3일 때 다시 재귀가 호출되고 이는 다시 1~4를 탐색합니다.
                    // i = 4일 때 다시 재귀가 호출되고 이는 다시 1~4를 탐색합니다.
                    // 이런식으로 4개의 수를 2개 뽑을 때의 모든 경우의 수를 확인할 수 있습니다.
            }
        }
    }

    public static void print(String str) {
        System.out.print(str);
    }
}

코드로 위와 같으며 그 결과는 다음과 같습니다. ( 4 2 )

1 1 
1 2 
1 3 
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3 
4 4

이는 M개를 뽑을 때까지 applyNum(이때까지 뽑은 수)를 더해주며, applyNum가 M개(2개)가 되면 더 이상 재귀호출을 하지 않는 방식으로 이루어져 있습니다.
for문으로 1~N까지 반복하는데 M번만 재귀를 부를 수 있고, M번 재귀 후 \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이므로

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

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

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

---

중복되는 수를 제외시키기

이렇게 완성한 것은 중복 여부를 확인하지 않아 모든 케이스만을 탐색하므로, 중복되는 것을 제외시켜주는 코드를 추가해줍니다.
저는 스택을 사용했습니다.

 static Stack<Integer> alreadyIn;
 alreadyIn = new Stack<>();
   if (!alreadyIn.contains(i)) {
                    alreadyIn.push(i);
                    recur(applyNum, makingStr + " " + i);
                    alreadyIn.pop();
                }

한 번 재귀를 거칠 때마다 안에 있는지 검사한 후, 없으면 스택에 넣고 재귀가 끝날 때마다 하니씩 회수하도록 했습니다.
그러면 끝납니다 : )

---

두 번째로 풀었을 때

이전보다 코드길이도 줄어들고 실행시간도 많이 줄였네요ㅜㅜ

import java.util.Scanner;

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

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

        nextPermitation(0);

        System.out.println(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++) {
                if(!isVisited[i]) {
                    isVisited[i] = true;
                    result[apply] = i;
                    nextPermitation(apply+1);
                    isVisited[i] = false;
                }
            }

        }
    }
}

isVisited배열을 사용해서 이전에 사용했던 숫자가 아닌 경우에만 다음 재귀를 호출할 수 있도록 했습니다. 만약 해당 재귀가 끝난다면,
예) 4 4 입력 시
맨 첫번째 1을 뽑으면 두 번째 재귀(두번째 수를 뽑을 때)에서 1을 재귀로 다시 호출하지 않습니다.
1 1 1 1
1 1 1 2
1 1 1 3
1 1 1 4
1 1 2 1
1 1 4 4
1 2 <대신 이 때에는 두 번재 재귀가 호출됩니다.
1 2 3 < 그다음 세번째 재귀
...
1 2 3 1
1 2 3 2
1 2 3 3
1 2 3 4 < 4개 다 뽑았으므로 출력버퍼에 넣어둠
이렇게 완전히 중복이 없을 때까지는 다음 재귀로 가지 못합니다.