[백준] 1039번 교환 (자바)

https://www.acmicpc.net/problem/1039

1039번: 교환

 

---

교환 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

16687

3698

2760

22.549%

문제

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

 

 

풀이 : 

BFS 문제로 숫자의 i 번째, j 번째 교환하는 연산을 K 번 했을 때 나타나는 최대값을 구하는 문제이다. 

 

K 번 도중에 나오는 숫자는 최대값 산정에 포함되지 않는다. 

 

K 번 도중에 같은 연산 횟수에서 같은 숫자가 나오는 것을 방지를 위해 Map Entry를 사용해서 문자열(숫자), 연산횟수 를 Set에 저장해서 풀었다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{

    public static void main(String[]args)throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] tmp = reader.readLine().split(" ");
        String N = tmp[0];
        int K = Integer.parseInt(tmp[1]);

        Queue<String[]> queue = new LinkedList<>();
        Set<Map.Entry<String, Integer>> set = new HashSet<>();

        queue.add(new String[]{N, "0"});
        set.add(new AbstractMap.SimpleEntry<>(N, 0) );

        int max = -1;

        while(!queue.isEmpty()) {
            String[] q = queue.poll();
            int count = Integer.parseInt(q[1]);

            if (count >= K) {
                max = Math.max(Integer.parseInt(q[0]), max);
                continue;
            }

            for(int i = 0; i<q[0].length()-1; i++) {
                for(int j = i+1; j<q[0].length(); j++) {
                    String result = swap(q[0], i, j);
                    Map.Entry<String, Integer> pair = new AbstractMap.SimpleEntry<>(result, count+1);

                    if (!set.contains(pair) && !result.startsWith("0")) {
                        queue.add(new String[]{result, (count+1)+""});
                        set.add(pair);
                    }
                }
            }
        }

        System.out.println(max);
    }

    public static String swap(String s, int i, int j) {
        char[] chars = s.toCharArray();

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

        return new String(chars);
    }

}