[JAVA] BOJ(백준) - N과 M(1) - 15649

-  문제내용

---

- 문제 접근 방법(내 생각)

첫번째 접근 방법(시간 초과남)

• 자연수 1~N까지의 숫자로 만들수 있는 모든 경우의 수를 고려해 수의 조합을 만든다.
• 수를 조합하기 위해 1~N까지 자연수를 받는 String[] kindN 배열을 초기화 해준다.
• kindN 배열의 길이만큼 재귀를 통해 for문을 반복적으로 돌면서 요소 하나하나를 String temp 에 붙여준다.
• 해당 요소에 볼일이 끝나면 temp의 맨뒤의 문자를 빼준다.
• 재귀의 종료조건은 temp의 길이가 M과 같을때로 설정한다.

- 내코드(시간 초과)

import java.util.*;
public class BOJ_15649 {
	static ArrayList<String> list = new ArrayList<String>();
	
	public void seqence(String[] kindN, String temp, boolean[] check, int M) {
		//종료조건
        if(temp.length() == M*2) { //temp에 공백포함이 되므로 M*2일때로 조건설정.
			if(!list.contains(temp)) {
				list.add(temp.substring(0,temp.length()-1));//temp의 마지막 공백 제거후 추가.
				return;
			}
		}
		
		for(int i=0; i<kindN.length; i++) { //kindN의 요소만큼 돌면서 확인
			if(check[i]) {continue;} //kindN요소에서 이미 방문한것은 for문 돌지 않음.
			
			temp += kindN[i]+" "; //temp에 공백을 포함하여 숫자를 조합함
			check[i]=true;
			
			seqence(kindN, temp, check, M); // 재귀함수 호출
			
			check[i]=false; //재귀종료 후 볼일이 끝난 i번째 요소는 다시 false로 바꿔줌.
			temp = temp.substring(0,temp.length()-2); //i번째 요소는 temp의 마지막 문자가 되고 마지막 문자는 공백을 포함해서 빼줌.
		}
	}
	
	public void solution(int N, int M) {	
		String[] kindN = new String[N]; //kindN배열 생성
		String temp = ""; //조합되는 숫자를 담을 변수
		boolean[] check = new boolean[N]; //kindN의 어느 요소가 방문 처리가 됐는지 확인하기 위한 배열
		
		for(int i=0; i<N; i++) {
			kindN[i]=Integer.toString(i+1); //1~N까지 자연수를 kindN배열에 문자열로 삽입.
		}
        
		seqence(kindN,temp,check,M); //재귀함수 호출
        
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		sc.close();
		
		new BOJ_15649().solution(N, M);
			
		for(String x:list) {
			System.out.println(x); //list에 있는 모든 요소 출력
		}
	}
}

앞에서 말했다시피 이렇게 코드를 작성하면 가독성도 떨어질 뿐만 아니라  시간초과가 난다... 어째서 시간 초과가 나는건지는 아직 모르겠는데 그냥 추측하기로는 temp 문자열을 반복적으로 추가, 수정하는 작업을 하게 돼서 그런거 아닐까한다(왜그런지 아는시는분 있으면 알려주셨으면ㅠㅠㅠㅠ...). 그래서 다른 사람들 코드를 살펴보니 kindN배열이나 temp문자열 필요없이 작성된 코드들이 있었다. 아래에서 살펴보자.

---

두번째 접근 방법

• 입력값 N,M은 전역변수로 설정.
• check 와 result 배열은 재귀함수의 매개변수로 넣어도 되지만 어차피 안에 요소들이 계속 재할당 되는 요소들이라전역변수로 설정
• result배열의 크기를 조건 M길이만큼의 크기로 설정해줌으로써 result에 모든 요소가 다찼을때 출력해보면 원하는 길이의 수열이 만들어짐.
• depth는 트리에서 깊이?라고 생각하면 될듯... 코드상에서 보면 depth자체는 자릿수를 의미하는 것으로 이해함.
• for문을 1~N까지 돌면서 result에 자연수 i를 depth자릿수에 채워 넣음.
• result 출력 후 마지막 자리(요소)는 false처리 해가면서 자리수마다 방문안한 자연수로 재할당 해줌 

- 다른사람 코드

import java.util.*;
public class BOJ_15649 {
	static int N,M; //N,M은 입력받고 바뀌지 않으므로 전역변수로 설정
	static boolean[] check; //check 배열로 i 인덱스 방문여부 결정
	static int[] result; //숫자의 조합을 위한 배열
	
	public void seqence(int N, int M, int depth) {
    	//재귀함수 종료조건
		if(depth==M) { //M길이 만큼의 숫자가 result에 요소로 들어갔다는 말.
			for(int x=0; x<result.length; x++) { //for문을 돌며 result 요소를 출력.
				System.out.print(result[x]+" ");
			}
			System.out.println(); //개행
			return;
		}
		
		for(int i=1; i<=N; i++) {
			if(check[i]) {continue;} //i 즉, 자연수 i가 방문됐던 요소라면 다음 i로 처음부터.
			
			result[depth]=i; //result에 자연수 i를 depth번째 자리로 할당.
			check[i]=true; //자연수 i를 방문처리.
			
			seqence(N,M,depth+1); //재귀호출하면서 지금까지 만든 수열 다음 자리에 1~N사이의 자연수를 넣으려고 depth에 +1 해줌.
			check[i]=false; //재귀가 종료될때마다 자연수 i에 해당하는 수는 다시 false 처리해서 방문할수 있게끔 만듦.
			
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		sc.close();
		
		result = new int[M]; //M길이 만큼의 수열을 만들어야하기 때문에 M크기 배열로 설정.
		check = new boolean[N+1]; //입력값 N은 1~N 자연수를 말하기 때문에 1부터 시작하려고 N+1로 크기 설정
		
		new BOJ_15649().seqence(N,M,0); //재귀 호출
	}
}

다른사람 코드와 내가 짯던 코드의 가장큰 차이점은 String 배열이나 문자열을 만들지 않고 단지 수열을 만들기위한 result배열하나만 존재한다는 점과 가독성면에서 큰차이가 있다... 또 내코드의 경우 list에 완성된 temp문자열을 전부넣고 마지막에 출력하는 반면 다른사람 코드는 result배열을 이용해 배열이 꽉찼을때 바로바로 요소를 쭉 출력해주고, 요소들을 다른 자연수로 다시 재할당 해주는 매우 간편해보이는 코드이다.

---

- 마치며

내 블로그 첫글인데 잘 정리해서 쓴건지 나도 잘 모르겠다. 일기쓰는 느낌;; 여튼 재귀관련 문제를 2문제째 풀어보는데 아직 재귀를 어떻게 사용해야할지 감이 잘안잡힌다. 그래도 처음에 재귀관련 코드를 봤을때 코드를 봐도 이해가 안됐는데 지금은 100은 아니여도 어느정도는 이해가 가능한 수준으로 발전한것에 감사하고 나중엔 더 발전된 코드로 알고리즘을 짤수 있도록 공부를 더 해야겠다!!!!