[백준 1039] 교환 - JAVA

WTS·2025년 11월 24일

BFS 백준 코딩테스트

코딩 테스트

목록 보기

6/81

문제

$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$ 을 출력한다.

접근 방법

처음에는 단순 그리디 문제로 판단하고 아래와 같은 방법으로 그리디를 생각했습니다.

가장 높은 자릿수부터 높은 수로 변환
가장 높은 숫자가 여러 개인 경우 낮은 자릿수의 숫자 먼저 변경
1. 가장 최고의 숫자로 변경했는데도 $K$ 가 남는 경우
  3-1. $K$ 가 짝수일 경우 유지 $3-2. $$K$ 가 홀수일 경우 그 다음으로 큰 숫자 만들기
  3-3. 만약 같은 숫자가 존재하는 경우에는 그대로 유지

그렇지만 위의 방식으로는 반례가 발생하게 되었습니다.

예시

$N = 7699$
$K = 2$
라고 가정하면

만들 수 있는 가장 큰 수는 $9976$ 이지만
위의 로직에 의하면

첫 번째에 $9697$
두 번째에 $9967$ 이 됩니다.

결론적으로 각각의 교환 회차에서 가장 높은 수로 교환하는 것이
최종적으로는 항상 높은 수가 된다는 제 생각이 틀렸다라는 것입니다,

그렇다면 해야될 것은
이 문제를 그리디로 볼 것이 아니라 모든 경우의 수를 탐색하는
브루트포스와 같은 방식을 생각해야합니다.

하지만 탐색되는 동안 중복되는 숫자는 없도록 가지치기를 해야하기에
BFS와 같이 visited를 적용해서 메모이제이션을 사용했습니다.

visited[k][max] 배열을 생성할 때
visited[i][j]는 교환 횟수가 i번 남았을 때의 숫자 j를 의미하고
만약 해당 원소가 true로 되어있을 경우
다음 방문(중복되는 연산)에 대해 가지치기를 수행했습니다.

코드

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

class Change {
    int n;
    int k;

    public Change(int n, int k) {
        this.n = n;
        this.k = k;
    }
}

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        System.out.println(change(N, K));
    }

    private static String change(int number, int maxK) {
        String s = String.valueOf(number);
        int L = s.length();
        int[] numbers = new int[L];
        int maxNumber = (int) Math.pow(10, L);

        if (L == 1 || (L == 2 && s.charAt(1) == '0')) {
            return "-1";
        }

        if (L == 7) {
            return "1000000";
        }

        boolean[][] visited = new boolean[maxK +1][maxNumber];
        Queue<Change> q = new ArrayDeque<>();

        visited[maxK][number] = true;
        q.offer(new Change(number, maxK));

        int max = 0;

        while (!q.isEmpty()) {
            Change change = q.poll();
            int n = change.n;
            int k = change.k;

            if (k == 0) {
                max = Math.max(max, n);
                continue;
            }

            setNumbers(numbers, n, L);

            for (int i = 0; i < L - 1; i++) {
                for (int j = i + 1; j < L; j++) {
                    if (i == 0 && numbers[j] == 0) continue;
                    int next = changeNumber(numbers, i, j);
                    if (!visited[k-1][next]) {
                        visited[k-1][next] = true;
                        q.offer(new Change(next, k-1));
                    }
                }
            }
        }

        return String.valueOf(max);
    }

    private static void setNumbers(int[] numbers, int n, int L) {
        int i = L - 1;

        while (n > 0) {
            numbers[i] = n % 10;
            n /= 10;
            i--;
        }
    }

    private static int changeNumber(int[] numbers, int i, int j) {
        int tmp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = tmp;

        int returnNumber = convertInt(numbers);

        numbers[j] = numbers[i];
        numbers[i] = tmp;

        return returnNumber;
    }


    private static int convertInt(int[] numbers) {
        int L = numbers.length;
        int mul = 1;
        int number = 0;

        for (int i = L - 1; i >= 0; i--) {
            number += numbers[i] * mul;
            mul *= 10;
        }

        return number;
    }
}