[백준] 10597. 순열장난 (자바 JAVA)

[ 문제 ]  [백준] 10597. 순열장난 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/10597

10597번: 순열장난

---

# 접근 방법 및 풀이 

 

• dfs + 백트래킹으로 풀었다.
• 처음에 아이디어 떠올리기가 힘들었는데 범위를 보고 아이디어를 떠올렸다.
• 순열은 최소 1~50개의 수로 이루어져있고, 1부터 N까지의 수로 이루어졌으므로 최대로 나올 수 있는 숫자가 50이다. 즉 숫자의 범위는 1~50이므로 자리수는 1자리 아님 2자리이다.
  

  4111109876532​

• 따라서 예제처럼 다음과 같이 문자열이 주어졌을 때, 문자열을 한자리씩 끊거나 두자리씩 끊어서 공백을 더한 정답 문자열을 만들어 주면 된다.
• idx = 0부터 시작해서 substring으로 한자리를 만들어주거나 두자리로 새로운 String을 만들었다.
• 이때 두자리씩 끊을때는 문자열 최대 범위를 넘지 않게 idx < len-1일 경우에만 살펴본다.
• 만든 String을 int로 바꿔서 최대값을 구했다. 이유는 순열은 1~N까지 구성되므로 최대값이 N이 되기 때문이다.
• 이렇게 만든 숫자들을 visit체크해서 1~N까지 범위를 살펴보고, 쭉 true라면 정답배열이 된다. 정답배열일때 print로 찍고 함수를 종료시켰다.
• 그리고 visit체크할 때 백트래킹처리 해주면 된다.
• 자세한건 코드참조

# 주의할 점 

 

• 두자리로 만든 숫자가 51보다 작아야함

 

JAVA 코드

package Silver;

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

public class bj10597_순열장난 {
	static String s;
	static boolean visit[];
	static int len;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		s = in.readLine();
		len = s.length();
		visit = new boolean[51];
		dfs(0, 0, "");
	}
	private static void dfs(int idx, int N, String ans) {
		if(idx == len ) {
			for (int i = 1; i <= N; i++) {
				if(!visit[i])
					return;
			}
			System.out.println(ans.trim());
			System.exit(0);
			return;
		}
		
		String tmp = s.substring(idx, idx+1);
		int num = Integer.parseInt(tmp);
		if(!visit[num]) {
			visit[num] = true;
			dfs(idx+1, (num > N)? num : N, ans+" "+tmp);
			visit[num] = false;
		}
		if(idx < len-1) {
			tmp = s.substring(idx, idx+2);
			num = Integer.parseInt(tmp);
			if(num < 51 &&!visit[num]) {
				visit[num] = true;
				dfs(idx+2, (num > N)? num : N, ans+" "+tmp);
				visit[num] = false;
			}
		}	
	}
}

 

 

 

REVIEW

조금 신박한 문제였다!