백준 1039 - 교환 (Java)

https://www.acmicpc.net/problem/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

예제 입력 2 복사

132 3

예제 출력 2 복사

312

예제 입력 3 복사

432 1

예제 출력 3 복사

423

예제 입력 4 복사

90 4

예제 출력 4 복사

-1

예제 입력 5 복사

5 2

예제 출력 5 복사

-1

예제 입력 6 복사

436659 2

예제 출력 6 복사

966354

 

풀이

문자열과 숫자를 섞어서 사용했다. 일단, M을 구하기 위해 문자열로 변환 후 length를 구했고, i와 j를 이 length 안에서 구하도록 했다.

또 위치를 바꾸기 위해 해당 문자열을 toCharArray로 변환 후 위치를 바꿔주었다.

조건 중 -1이 나오는 경우는 앞의 수가 0이 될 때 밖에 없기 때문에 charArr[0]이 0일 경우를 봐주었고

K번을 다 돌고 나서 Max값을 구하기 위해 그 전에는 갱신하지 않았다.

그 외에 탐색은 그냥 BFS 안에 i,j 선택해서 숫자 만들어주는 것 밖에는 없다.

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

public class BJ_1039_교환 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Queue<String> queue = new ArrayDeque<>();
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] visited = new int[1000001];

        String str = String.valueOf(N);
        int length = str.length();
        int answer = 0;

        queue.add(str);
        while(!queue.isEmpty()&& K>0)
        {
            int size = queue.size();
            for(int t=0; t<size; t++)
            {
                String temp = queue.poll();
                for(int i=0; i<length-1; i++)
                {
                    for(int j=i+1;j<length;j++)
                    {
                        char[] charArr = temp.toCharArray();
                        char charTemp = charArr[i];
                        charArr[i] = charArr[j];
                        charArr[j] = charTemp;
                        String numStr = new String(charArr);
                        int number = Integer.parseInt(numStr);
                        if((numStr.charAt(0)!='0') && visited[number]!=K)
                        {
                            queue.add(numStr);
                            visited[number]=K;
                        }
                    }
                }
            }
            K--;
        }
        if(queue.isEmpty())
            System.out.println(-1);
        else{
            for(String num : queue)
            {
                answer = Math.max(Integer.parseInt(num),answer);
            }
            System.out.println(answer);
        }

    }
}