[백준]1039: 교환(java)

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

1039번: 교환

문제

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

16375 1

예제 출력 1 

76315

---

풀이

swap을 1번 > 2번 > 3번 .. > K번 해야하는 경우다.

각 스탭별로 나온 케이스를 다음 케이스에서 활용해야하므로 BFS를 떠올렸다.

1번 swap한걸 q에 담고 그 q를 또 스왑하면 그게 2번 swap한 case가 된다.

여기서 주의해야할 점은 N번 swap이 일어난 후 N+1번 swap을 할 때 visited를 초기화해야한다. 이전에 swap한 것과 같은 경우가 발생할 수 있기 때문이다. 이 과정을 빼먹으면 답이 이상하게 나올 수 있다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G3_1039_교환 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashSet<String> visited;
        Queue<String> queue = new LinkedList<>();
        String str = st.nextToken();
        queue.add(str);
        int K = Integer.parseInt(st.nextToken());
        int N = str.length();
        int max = -1;

        for(int k=0; k<K; k++) {
            visited = new HashSet<>();
            int size = queue.size();

            for(int q = 0; q < size; q++) {
                String nowStr = queue.poll();

                for(int i=0; i<N-1; i++) {
                    for(int j = i+1; j<N; j++) {
                        if(i==0 && nowStr.charAt(j) == '0') continue;
                        String swapStr = swap(nowStr, i, j);
                        if(visited.contains(swapStr)) continue;
                        visited.add(swapStr);
                        queue.add(swapStr);

                        if(k==K-1) {
                            max = Math.max(max, Integer.parseInt(swapStr));
                        }
                    }
                }
            }
        }
        System.out.printf("%d", max);
    }

    private static String swap(String str, int i, int j) {
        StringBuilder swapStr = new StringBuilder();
        swapStr.append(str);
        swapStr.setCharAt(i, str.charAt(j));
        swapStr.setCharAt(j, str.charAt(i));

        return swapStr.toString();
    }
}