[백준] 16943 숫자 재배치 - Backtracking / Java

• 문제 링크

16943번: 숫자 재배치

 

• 풀이 과정

입력받은 문자열 a를 순열으로써 charAt() 으로 인덱스를 탐색하고, boolean 배열을 활용한 백트래킹으로 구한다.

 

이때 문제에 주어진 조건 상 구해진 순열이 0 으로 시작하면 안되고 b 보다 작거나 같아야 하므로

순열의 하나의 경우의 수를 c 이고 탐색을 수행할 반복문의 인덱스를 i 라고 할 때,

현재 문자열 a 에서 탐색한 숫자가 0 이거나 (a.charAt(i) - '0' == 0),

구해진 순열이 b 보다 클 경우 (Integer.parseInt(c + a.charAt(i)) > b) 해당 인덱스를 건너뛴다.

 

이러한 조건에 의해 구해진 순열과 현재까지 구해진 순열 중 큰 수를 res 변수에 갱신시켜 정답으로써 출력하며

만약 res 변수가 갱신된 적이 없다면 b 보다 작은 c 가 없으므로 기본값 -1 을 출력한다.

 

• 풀이 코드

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

public class Main {

	static String a;
	static int b;
	static int res = -1;
	static boolean[] visit;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		a = st.nextToken();
		b = Integer.parseInt(st.nextToken());
		visit = new boolean[a.length()];

		recur("", 0);

		bw.write(res + "\n");
		bw.flush();
	}

	private static void recur(String c, int depth) {
		if (depth == a.length()) {
			res = Math.max(res, Integer.parseInt(c));
			
			return;
		}

		for (int i = 0; i < a.length(); i++) {
			if (visit[i])
				continue;
			if (a.charAt(i) - '0' == 0 && depth == 0)
				continue;
			if (Integer.parseInt(c + a.charAt(i)) > b)
				continue;

			visit[i] = true;
			recur(c + a.charAt(i), depth + 1);
			visit[i] = false;
		}
	}

}