[JAVA] BOJ(백준) - N과 M(2) - 15650

- 문제 내용

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

참고로 처음에 나는 문제 이해를 중복제외한 모든 수열이 출력되고 출력된 수열을 오름차순 하는건줄 알고 예제 출력이 잘못됐나 생각했는데,

그게 아니라 수열 하나의 경우에 한해서 오름차순을 진행하는 것이였다ㅠㅠ,, 헷갈리지말자..

---

- 문제 접근 방법

기존에 풀었던 N과 M(1) 문제랑 매우 유사한 문제이다. 이 문제는 수열 하나를 만들때 오름차순을 고려해야 하므로 전의 값을 알고 있어야한다고 생각했다. 그래서 전의 값을 저장할 변수를 하나 만들어주고 수열을 만들때 다음 값부터는 전의 값이 할당된 변수와 이제 들어올 값을 비교해 오름차순의 조건이 되면 값에 입력해주는 방법으로 진행했다.

하지만,,, 풀고나서 다른 분의 너무 간결하고 좋은 코드를 보니 현자타임이 왔었다.. 여튼 위에서 말한 방법에서 필요한 건

• 크기가 M이 될 수열을 넣고 찍어낼 배열 1개
• 수의 범위가 1~N까지 일때 어떤 수를 방문했는지 여부를 체크할 배열 1개
• 재귀함수 실행시 전의 값을 저장할 변수 1개
• 재귀함수 종료조건, 수열의 길이가 M일때를 알수 있도록 해주는 변수 1개

총 4가지가 필요했다. 아래서 코드를 보자!

---

- 풀이

package org.boj.nm;

import java.util.Scanner;

public class BOJ_15650_1 {
	static int N,M;
	static int temp; //전의 값을 담을 변수
	static boolean[] check; //방문여부를 확인할 배열
	
	public void solution(int depth, int[] arr) {
		if(depth==M) {
			for(int x:arr) {
				System.out.print(x+" ");
			}
			temp=0;
			System.out.println();
			return;
		}
		
		for(int i=1; i<=N; i++) {
			if(check[i]) {continue;}

			arr[depth] = i;	
			int preTemp = temp; //재귀 실행시 temp값을 저장해 놓아야할 변수.
			 
			if(temp<arr[depth]) { //전의 값이 이제 들어올 값보다 작다면 오름차순이 되므로 실행.
				check[i]=true; 
				temp = arr[depth]; //temp에 최근 수를 넣어줌.
				
				solution(depth+1,arr);
				
				temp = preTemp; //재귀 끝나면 저장했던 temp값을 원래대로 돌려줌.
				check[i]=false; 
			}//if			
		}//for
	}//solution

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		sc.close();
		
		check = new boolean[N+1]; //1~N까지라서 N+1크기로.
		int[] arr = new int[M]; //만들어진 수열을 찍어낼 배열
		
		new BOJ_15650_1().solution(0,arr);
	}
}

 

temp값을 preTemp라는 변수에 넣어 둬야한다. 처음에는 preTemp 변수를 고려하지 않았는데 그렇게 해서 코드를 돌리면 원하는 수열의 값이 다 출력되지 않는다. 이유는 재귀가 끝났을때 전에 temp값을 다시 원래대로 돌려 놓지 않았기 때문에 temp에는 마지막 제일 큰 수(i , arr[depth])가 저장되게 되고 그러면 앞으로 더 수행할 재귀가 남아있음에도 if문에서 걸러지기 때문에 그렇다.

그래서 중요한건 재귀를 풀때 어떤 특정 값을 저장해놓고 사용할꺼라면 반드시 재귀가 종료될때 전의 값으로 돌려놔야한다(check 배열과 같은 원리). 

그리고 아래는 다른분 코드를 참고해서 풀었는데 훨씬 간결하고 입력,출력도 효율성이 좋다..

---

package org.boj.nm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_15650_2 {
	static int N, M;
	static int[] arr;
	public static StringBuilder sb = new StringBuilder();
	
	public void solution(int depth, int temp) {
		if(depth==M) {
			for(int x:arr) {
				sb.append(x).append(" ");
			}
			sb.append("\n");
			return;
		}
		
		for(int i=temp; i<=N; i++) {
			
			arr[depth] = i;			
			solution(depth+1, i+1);			
			
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		
		arr = new int[M];
		
		
		new BOJ_15650_2().solution(0,1);
		
		System.out.println(sb);
	}
}

원리는 같은데 이 경우 입력을 BufferedReader를 사용했고, 출력도 배열을 사용한게 아니라 값이 변하는 문자열에 유리한 StringBuilder를 사용하면서 출력도 효율적으로 했다.

그리고 재귀부분의 for Loop가 temp부터 시작하면서 재귀함수의 매개변수에 i+1을 해줘서 수의 중복여부는 당연히 없어져서 check배열이 필요없고, 재귀함수의 매개변수를 i+1을 해줌으로 자연스럽게 오름차순으로 수열이 만들어진다.

만약 i+1이 아니라 temp+1을 해버리면 현재까지 진행된 수에서 다음 수로 넘어가는게 아니라 temp로 시작했던 수에서 temp+1인 수로 넘어가기 때문에 수의 중복이 있는 수열도 출력되게 된다. 주의하자!

---

- 마치며

재귀함수에서 어떤 특정값을 저장하고 사용할꺼라면 반드시 재귀가 끝날때 원래의 값으로 돌려놔야한다는 것을 잊지말자! 그리고 다른 사람 코드를 참조할때 내가 먼저 충분히 고민하고 다른사람 코드를 봐야 이해도 쉽고 효율적인것 같다.