0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.
1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.
위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.
첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.
첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.
16375 1
76315
132 3
312
이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int max = -1;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
bfs(input[0], Integer.parseInt(input[1]));
System.out.println(max);
}
public static void bfs(String start, int cnt_max) {
Queue<Pair> queue = new LinkedList<>();
boolean[][] visited = new boolean[1000001][11]; //중복 체크를 위한 boolean 배열
visited[Integer.parseInt(start)][0] = true;
queue.add(new Pair(start, 0));
StringBuilder sb;
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(temp.cnt==cnt_max) {
max = Math.max(max, Integer.parseInt(temp.str));
continue;
}
for(int i=0; i<temp.str.length()-1; i++) {
char c1 = temp.str.charAt(i);
for(int j=i+1; j<temp.str.length(); j++) {
sb = new StringBuilder(temp.str);
char c2 = sb.charAt(j);
if(i==0 && c2=='0') continue; //0이 맨 앞에 오는 경우 체크
sb.replace(i, i+1, Character.toString(c2));
sb.replace(j, j+1, Character.toString(c1)); //자리 교환
if(visited[Integer.parseInt(sb.toString())][temp.cnt+1]) continue; //중복
visited[Integer.parseInt(sb.toString())][temp.cnt+1] = true;
queue.add(new Pair(sb.toString(), temp.cnt+1));
}
}
}
}
public static class Pair {
String str;
int cnt;
public Pair(String str, int cnt) {
this.str = str;
this.cnt = cnt;
}
}
}