백준 16943번: 숫자 재배치

문제 설명

• https://www.acmicpc.net/problem/16943
• A를 변형해 만든 여러 C들 중 가장 큰 C를 구하는 문제입니다.

접근법

• 백트래킹으로 모든 C를 구합니다.
• 1000을 변형한 0001은 1로 취급하지 않습니다.
  • 문제에 딱히 조건이 명시되어 있지는 않은데 예제2번을 통해 안된다는 걸 확인할 수 있습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int maxVal = -1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		st = new StringTokenizer(br.readLine());
		String A = st.nextToken();
		String B = st.nextToken();
		permu(0, 0, A.length(), new char[A.length()], new boolean[A.length()], A, B);
		System.out.println(maxVal);

	}

	public static void permu(int start, int depth, int N, char[] answer, boolean[] v, String A, String B) {
		if (depth == N) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < N; i++) {
				sb.append(answer[i]);
			}
			if (answer[0] == '0')
				return;
			String C = sb.toString();
			if (A == C)
				return;
			if (Integer.parseInt(C) < Integer.parseInt(B)) {
				maxVal = Math.max(maxVal, Integer.parseInt(C));
			}
			return;
		}
		for (int i = 0; i < N; i++) {
			if (v[i])
				continue;
			answer[depth] = A.charAt(i);
			v[i] = true;
			permu(i + 1, depth + 1, N, answer, v, A, B);
			v[i] = false;
		}
	}

}