문제
https://www.acmicpc.net/problem/1039
풀이
서로 다른 인덱스 i, j 번째 있는 수들을 k번 교환해서 나오는 최댓값을 구하는 문제이다.
처음에 누구나 백트래킹을 해보고 싶다는 생각이 들 것이다.
그런데, 서로 다른 인덱스 2개를 고르는 수의 최댓값은 49이다.
그러면 49^10이 되는 것인데, 무조건 시간 초과가 날 것이다.
그러면 문제를 k번 바꿔서 만들 수 있는 수들을 어떻게 만들 수 있을까? 라는 것으로 다르게 생각해보면 된다.
= k번째가 되었을 때 최댓값을 갱신을 해주면서, (현재 숫자,바꾼 횟수)를 가진 bfs를 수행해보는 것이다.
그러면 시간복잡도는 10 * 1,000,000 이므로 1000만 연산으로 문제를 해결할 수 있다.
1. n, k를 입력받고 입력받은 수의 길이를 기록한다.
2. (변경된 숫자, 바꾼 횟수)를 가진 bfs를 수행하고 k번째가 되었을 때 최댓값을 갱신한다.
3. 최댓값을 리턴한다.
소스코드
import java.io.*;
import java.util.*;
public class Main {
static StringTokenizer st;
static int length;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine(), " ");
answer = -1;
String s = st.nextToken();
length = s.length();
int n = Integer.parseInt(s);
int k = Integer.parseInt(st.nextToken());
bfs(n, k);
System.out.print(answer);
br.close();
}
static void bfs(int n, int k) {
ArrayDeque<int[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[100_0001][k + 1];
queue.addLast(new int[] {n, 0});
visited[n][0] = true;
while(!queue.isEmpty()) {
int[] arr = queue.removeFirst();
int num = arr[0];
int cnt = arr[1];
if (cnt == k) {
answer = Math.max(answer, num);
continue;
}
for (int i = 0; i < length - 1; i++) {
for (int j = i + 1; j < length; j++) {
int next = swap(num, i, j);
if (next != 0 && !visited[next][cnt + 1]) {
queue.addLast(new int[] {next, cnt + 1});
visited[next][cnt + 1] = true;
}
}
}
}
}
static int swap(int num, int x, int y) {
char[] arr = String.valueOf(num).toCharArray();
char temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
if (arr[0] == '0') {
return 0;
}
StringBuilder sBuilder = new StringBuilder();
for (char ch : arr) {
sBuilder.append(ch);
}
return Integer.parseInt(sBuilder.toString());
}
}
실행결과

'Problem Solving > Baekjoon' 카테고리의 다른 글
| [Baekjoon] LCS - Java (0) | 2025.09.06 |
|---|---|
| [Baekjoon] DSLR - Java (0) | 2025.09.04 |
| [Problem Solving] 코딩테스트 준비 전략 (0) | 2025.08.25 |
| [Baekjoon] 감소하는 수 - Java (0) | 2025.08.23 |
| [Baekjoon] 과일 탕후루 - Java (0) | 2025.08.21 |