[Baekjoon] 교환 - Java

문제

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());
    }
}

 

실행결과