문제

https://www.acmicpc.net/problem/1039
0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

풀이

접근방법

시간제한이 2초, 메모리가 128MB.

각각의 경우를 시뮬레이션 하며 정답을 찾는 문제.
K가 최대 10이므로 BFS로 접근.

1. 각 단계마다 버블소트와 유사하게 하나씩 비교해가며 숫자를 만들어본다.
2. 만들어 본적이 있다면 생략, 없다면 만들어서 큐에 삽입 ( 다음 depth에서 계산하기 위함)
3. 1-2를 K번 반복.
4. 만들어진 수열 중 최대값을 찾는다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int N, K;
	static boolean[] check;
	static int len;

	static class Data {
		int[] arr;

		Data() {
		}

		Data(int value) {
			init(Integer.toString(value));
		}

		public void init(String n) {
			int size = n.length();
			arr = new int[size];
			for (int i = 0; i < size; ++i)
				arr[i] = n.charAt(i) - '0';
		}

		public int getValue() {
			int result = 0;
			for (int i = 0; i < arr.length; ++i) {
				result += arr[i];
				result *= 10;
			}
			return result / 10;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] splitedLine = in.readLine().split(" ");

		N = stoi(splitedLine[0]);
		K = stoi(splitedLine[1]);
		len = splitedLine[0].length();

		Data start = new Data();
		start.init(splitedLine[0]);

		Queue<Data> q = new ArrayDeque<>();
		q.add(start);

		int depth = 1;
		while (!q.isEmpty()) {
			check = new boolean[1000001];
			if (depth > K)
				break;
			int size = q.size();
			while (size-- > 0) {
				Data d = q.poll();

				// 버블소트처럼 하나씩 비교하며 바꿔본다.
				for (int i = 0; i < len - 1; i++) {
					for (int j = i + 1; j < len; j++) {
						int value = change(d.getValue(), i, j);
						// 앞자리가 0이 되거나, 해당 depth에서 이미 만들었다면 생략한다.
						if (value != -1 && !check[value]) {
							check[value] = true;
							q.add(new Data(value));
						}
					}
				}
			}
			depth++;
		}

		// 최종적으로 만들어진 값 중에 최대값을 찾는다.
		int result = -1;
		while (!q.isEmpty()) {
			Data d = q.poll();
			result = Math.max(result, d.getValue());
		}
		System.out.println(result);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}

	private static int change(int value, int i, int j) {
		StringBuilder sb = new StringBuilder();
		sb.append(value);

		// 첫자리는 0이 될 수 없다.
		if (i == 0 && sb.charAt(j) == '0')
			return -1;

		char c = sb.charAt(i);
		sb.setCharAt(i, sb.charAt(j));
		sb.setCharAt(j, c);
		return Integer.parseInt(sb.toString());
	}
}