백준 10597번: 순열 장난 [재귀][백트래킹] -Java

 

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

10597번: 순열장난

 

문제 이해를 못하고 냅다 풀어서 아주 많은 틀렸습니다를 얻었던. . . . . .

 

엄청난 IF문을 통해 걸러내서 답을 찾아내게 되었다.

 

N을 구하는게 가장 키포인트.

주어진 수열의 길이를 통해서 N의 숫자를 구하면 된다.

9이하 일 경우에는 0~9 범위 내에서만 사용하기에 수열의 길이가 N이 된다.

10이상이면 두자리수가 되기에 (9+수열 길이)/2 를 해주어서 N을 구한다. 9를 더하는 이유는 0~9범위가 있으니!

나누기 2를 하는 이유는 최대 50개의 수라고 하니 최대 숫자는 50이므로 2자리 수 이기 때문이다.

 

그리고 이제 N을 구했으니 여러 IF를 붙여서 불필요한 재귀는 하지 않게 싹을 자르면 된다....zZz...

 

 

<Java코드>

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static int arr[];
	public static boolean use[];
	public static int N;
	public static String str = "";
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		str = br.readLine();
		
		N = str.length()<=9 ? str.length() : (str.length()+9)/2; //0~9까지 9개, 그외는 2자리 수
		use = new boolean[51];
		arr = new int[N];
		
		fun(0,0);

	}
	
	public static void fun(int idx, int cnt) {
		
		
		//종료조건
		if(cnt == N) {
			for (int i = 0; i < N; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}

		
		//재귀
		for (int i = 1; i <= 2; i++) { //2자리수가 최대 (최대 50개의 수, 1부터 N 순열)
		
			
			//이미 복구한 수열이 존재하는가?
			if(arr[N-1]>0)
				continue;
			
			//백트래킹- 0부터 시작하는 숫자인가?
			if(str.substring(idx).startsWith("0"))
				continue;
			
			//두자리수 파악 불가한지?
			if(idx+i-1 > str.length())
				continue;
			
			int num = Integer.parseInt(str.substring(idx,idx+i));
            
			if(num > 50)
				continue;			
			
			//백트래킹- 이미 사용한 숫자인가?
			if(use[num])
				continue;
			
			//백트래킹- N보다 큰 숫자 인가?
			if(num > N)
				continue;
			
			
			use[num]=true;
			arr[cnt]=num;
			fun(idx+i,cnt+1); 
			//다른 자릿수 경우의 탐색을 위한 원복 
			use[num]=false;
			
			
		}

		
		
	}
	

}