구현

백준 9081번을 자바를 이용해 풀어보았다.
문제 링크 첨부한다.
https://www.acmicpc.net/problem/9081

---

next_permutation 구현하기

결국 내 힘으로 풀지 못했고 index를 이용해야 풀리겠다는 막연한 생각만 하다가 다른 사람들의 풀이를 참고했다. c++에서는 라이브러리에서 제공되는 next_permutation을 직접 구현해야 한다는 것도 파악은 했지만 어찌 해야할지를 몰라서 결국 실패...

풀이를 올려둔 모든 사람들이 동일한 로직으로 풀었다고 글을 올려뒀지만 그렇게 해야하는 이유를 써둔 사람은 없었다. 다른 사람들에게는 너무 당연해서 이유를 굳이 쓸 필요가 없었나보다... 하지만 나에게는 모든 사람들이 똑같이 올려둔 로직이 당연하지 않아서 머리 굴리느라 시간이 좀 소요됐다.

다음은 풀이 로직이다.

1. 주어진 문자열의 맨 뒤에서 시작해, 앞으로 가면서 처음으로 '감소하는 원소'의 위치를 idx1 에 저장한다.
2. 다시 주어진 문자열의 맨 뒤에서부터 시작해, 1에서 찾은 '감소하는 원소'보다 큰 원소를 처음으로 만나면 그 원소의 위치를 idx2에 저장한다.
3. 1에서 찾은 '감소하는 원소'와 2에서 찾은 '큰 원소'를 swap 해준다. 
4. idx1 위치 이후에 있는 모든 원소들을 오름차순으로 정렬한다. 

이 로직을 보자마자 1 번 과정은 이해가 됐다. 하지만 그 이후가 잘 이해가 되지 않았다.

필요한 부분만 잘라보기

1은 이해가 됐기 때문에 사실 전체 문자열을 볼 필요없이 idx1의 위치부터만 잘라서 살펴보면 된다.

위 그림에서 어차피 앞 두 자리인 04 는 next_permutation 을 구하기 위해 신경 쓸 필요가 없다. 그렇다면 132만 살펴보면 된다.

idx1 자리의 숫자 1은 그 자리에서 할 일을 다 마친 것이다. 그렇다면 idx1 이후에 있는 모든 원소들 중에서 1보다 큰 원소들 중 가장 작은 녀석이 1의 역할을 대신 하러 들어와야 한다. 우리가 찾는 이 원소를 일단 target 이라 부르기로 하자.

여기까지도 생각은 했다. 근데 이 1보다 큰 원소들 중 가장 작은 녀석을 찾기 위해 왜 위 로직의 2 과정을 거쳐야 하는지 잘 이해가 안됐다. 차라리 idx1 뒤에 있는 녀석들을 따로 싹 오름차순 정렬해서 첫번째 자리에 있는 녀석을 찾는다면 이해가 되겠는데,,, 왜 문자열의 맨 뒤에서부터 탐색을 시작해 !!처음!!으로 만나는 녀석이 반드시 우리의 target이 될 수밖에 없는지는 잘 이해가 되지 않았다.

그래서 처음 만날 필요 없이 두 번째로 만나는 녀석이 target이 될 수 있다는 가정으로 시작하는 귀류법을 사용해봤다.
즉, 위의 예에서 살펴보자면 실제 우리의 target 인 2가 맨 뒤가 아닌 가운데에 오는 경우를 생각해보는 것이다. 그렇다면 문자열이 123 으로 바뀔텐데, 그럼 애초에 idx1의 자리에 1이 아닌 2가 오게 되고 맨 뒤의 2와 3만 swap 하고 바로 끝나는 것이다...

그래서 반드시 처음 만나는 녀석이 우리의 target이 될 수밖에 없다는 설명이 결국 이해가 됐다...

다음은 내가 제출한 전체 코드다.

import java.io.*;
import java.util.*;

public class boj9081 {
    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bfr.readLine());

        for(int i=0; i<N; i++){
            System.out.println(solution(bfr.readLine()));
        }
    }

    static String solution(String s){
        StringBuilder sb = new StringBuilder();
        int n = s.length();

        char[] ary = s.toCharArray();
        int idx1 = -1, idx2 = 0;

        for(int i=n-1; i>0; i--){
            if(ary[i-1]<ary[i]){
                idx1 = i-1;
                break;
            }
        }

        if(idx1==-1)    return s;

        for(int i=n-1; i>=0; i--){
            if(ary[idx1]<ary[i]){
                idx2 = i;
                break;
            }
        }

        char tmp = ary[idx1];
        ary[idx1] = ary[idx2];
        ary[idx2] = tmp;

        Arrays.sort(ary, idx1+1, n);
        for(char c: ary)    sb.append(c);

        return sb.toString();
    }
}

더 깊이 고민해보고 머리 터질 때까지 또 고민해보자... 오늘은 좀 힘겹긴 했지만 그래도 찝찝하게 넘어가지는 않아서 다행이다.