[BOJ] 1039. 교환 - (Java)

[BOJ] 1039. 교환 - (Java)

Problem

제출일 : 2020-03-21

문제 풀이 시간 : 2H

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/9019

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

Output

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

Example

input

16375 1

output

76315

Solution & Inpression

visit을 2차원 배열을 이용하여 처리

BFS를 이용한 완전탐색.

Code

언어 : JAVA

메모리 : 55052 kb

실행 시간 : 176 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static boolean visit[][];
    static int N, K, len;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        len = ("" + N).length();

        visit = new boolean[1000001][K + 1];

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { N, 0 });
        visit[N][0] = true;

        int result = -1;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[1] == K) {
                if (result < now[0]) {
                    result = now[0];
                }
                continue;
            }

            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    int next = solve(now[0], i, j);
                    if (next != -1 && !visit[next][now[1] + 1]) {
                        visit[next][now[1] + 1] = true;
                        q.add(new int[] { next, now[1] + 1 });
                    }
                }
            }

        }

        System.out.println(result);

    }

    private static int solve(int x, int i, int j) {
        char[] input = ("" + x).toCharArray();

        if (i == 0 && input[j] == '0')
            return -1;

        char tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;

        int ret = 0;
        for (int k = 0; k < input.length; k++) {
            ret *= 10;
            ret += input[k] - '0';
        }
        return ret;
    }
}