BOJ G2 1039 교환 JAVA

1039번: 교환

---

문제 읽기

일단 처음 문제를 읽었을 때는 그리디한 방식이 떠올랐다. 큰 숫자가 앞으로 올수록 좋을 것 같다고 생각했기 때문에, 맨 앞부터 숫자가 들어갈 자리를 정하고, 그 뒤의 숫자들 중에서 최댓값을 앞으로 땡기자는 생각이었다.

 

하지만 그렇게 했을 때 코드가 좀.. 여러가지 예외를 처리해 주면서 더러워졌을 뿐만 아니라, 잡지 못하는 예외 상황이 있었다. 그건 바로 숫자를 상호 “교환”하는 것이기 때문에, 최대인 수가 여러 개인 경우에 어떤 수와 교환할 지에 대한 문제였다.

 

이런 저런 문제와, 틀렸습니다 라는 문구, 그리고 질문 게시판에서 언뜻 bfs..라는 단어를 보고 그냥 완탐으로 푸는 게 맞다고 생각했다. 시간복잡도를 봤을 때도 주어지는 정수가 최대 7자리이고, 2^7 정도는 충분할 것이라 판단했다.

---

문제 풀기

나는 DFS로 풀었다. BFS로 많이 푼 거 같던데, 개인적으로 DFS가 좀 더 직관적으로 이해가 되는 것 같아 DFS로 해결했다.

 

풀이는 크게 복잡하지 않다. 정리해보자.

1. 우선 입력값을 받아 int[]에 저장한다. string을 나누면 char가 되기 때문에 char - ‘0’을 해주면 정수 값이 제대로 들어갈 것이다.
2. dfs를 돌린다. 인자는 **(입력 숫자의 배열, 교환할 위치(0부터), 교환된 횟수)**이다.
   1. target은 고정된 교환할 위치이다. 따라서 target+1부터 숫자를 교환해서 다음 dfs로 넘겨주었다.
   2. 이때 모든 경우를 다 고려하기 위해, 교환 해주거나, 안해주거나 두 가지 경우를 모두 적었다.
   3. 또한 target이 배열의 끝에서 두 번째 위치에 올 경우에는, 계속 남은 두 개만 교환하는 게 최댓값을 찾는데에 적합하다 생각하여 target을 증가하지 않고 바꾼 상태로 넘겨주었다.
      • 75321 → 75312 → 75321 → 75312
      이렇게 가장 끝의 두 자리만 계속 바꿔주는 것으로 가장 큰 값을 찾을 수 있다.
   4. 예시) 현재 75321로 정렬되었고, 아직 정렬되어야 할 횟수가 3회 남은 경우
   5. target의 위치가 0인 경우에는 0과 교환할 수 없기 때문에 안바꾸는 경우로 dfs 넘겨주고 continue로 패스 해주었다.
3. 만약 cnt == N, 즉 교환 횟수를 다 쓰면, 정수로 변환하여 비교하여 최댓값을 저장했다.

써놓고 보니까 조금 복잡하긴 하지만, 차근 차근 하면 풀릴 것이다!

 

그리고 아래 코드에서 조금 더 개선하면 시간복잡도도 더 줄일 수 있을 것 같다.

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_G2_1039_교환 {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        String input = st.nextToken();
        int[] nums = new int[input.length()];
        for (int i = 0; i < nums.length; i++){
            nums[i] = input.charAt(i) - '0';
        }
        N = Integer.parseInt(st.nextToken());

        dfs(nums.clone(), 0, 0);
        System.out.println(maxValue);
    }

    static int maxValue = -1;
    private static void dfs(int[] nums, int target, int cnt) {
        if (cnt == N){
//            System.out.println(Arrays.toString(nums));
            StringBuilder sb = new StringBuilder();
            for (int no : nums){
                sb.append(no);
            }
            int val = Integer.parseInt(sb.toString());
            maxValue = Math.max(maxValue, val);
            return;
        }
        for (int i = target+1; i < nums.length; i++){
            if (target == 0 && nums[i] == 0) {
                dfs(nums.clone(), target+1, cnt); //안바꿈
                continue;
            }

            int[] clone = nums.clone();
            int tmp = clone[i];
            clone[i] = clone[target];
            clone[target] = tmp;
            if (target == nums.length-2){
                dfs(clone.clone(), target, cnt+1); //바꿈
            }
            else{
                dfs(clone.clone(), target+1, cnt+1); //바꿈
                dfs(nums.clone(), target+1, cnt); //안바꿈
            }
        }
    }
}