문제
정수 N과 K가 주어진다. N의 두 자리를 K번 교환하여 만들 수 있는 가장 큰 수를 구한다.
- 교환 후 첫 자리가 0이 되면 안 된다.
- 정확히 K번 교환해야 한다 (같은 자리를 반복 교환 가능).
- 만들 수 없으면 -1을 출력한다.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ K ≤ 10)
출력
K번 교환 후 만들 수 있는 가장 큰 수를 출력한다. 불가능하면 -1을 출력한다.
예제
입력:
16375 2출력:
76315풀이
핵심 아이디어: DFS + 방문 체크(상태: 숫자 × 교환 횟수)로 모든 교환 경우를 탐색하고, 정확히 K번 교환했을 때의 최댓값을 구한다.
visit[숫자][교환 횟수]배열로 이미 방문한 상태를 체크하여 중복 탐색을 방지한다.- DFS로 현재 자릿수의 모든 두 자리 조합을 교환해본다.
- 교환 시 첫 번째 자리(인덱스 0)가 0이 되는 경우는 건너뛴다.
- 깊이가 K에 도달하면 현재 수와
result의 최댓값을 갱신한다. - 방문하지 않은 상태(
visit[새 수][depth+1] == false)만 재귀 호출하여 탐색 중복을 방지한다.
상태 공간: 최대 1,000,001 × 11개의 상태이므로 메모리 내에서 처리 가능하다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day199BOJ1039교환 {
public static int n, k, result = -1;
public static char[] temp;
public static boolean[][] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
visit = new boolean[1000001][k + 1];
temp = String.valueOf(n).toCharArray();
visit[n][0] = true;
dfs(0);
System.out.println(result);
br.close();
}
public static void dfs(int depth) {
if (depth == k) {
result = Math.max(Integer.parseInt(String.valueOf(temp)), result);
return;
}
for (int i = 0; i < temp.length - 1; i++) {
for (int j = i + 1; j < temp.length; j++) {
if (i == 0 && (temp[i] == '0' || temp[j] == '0'))
continue;
swap(i, j);
if (!visit[Integer.parseInt(String.valueOf(temp))][depth + 1]) {
visit[Integer.parseInt(String.valueOf(temp))][depth + 1] = true;
dfs(depth + 1);
}
swap(i, j);
}
}
}
public static void swap(int a, int b) {
char tempChar = temp[a];
temp[a] = temp[b];
temp[b] = tempChar;
}
}복잡도
- 시간: O(N × K × D^2) — N은 숫자의 최댓값, D는 자릿수(최대 7), K는 교환 횟수(최대 10)
- 공간: O(N × K) — 방문 배열 크기 1,000,001 × 11