백준 9081 단어 맞추기 자바(java)

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

9081번: 단어 맞추기

 

풀이 방법

알파벳을 숫자 1, 2, 3, 4...로 바꾸어 생각해본다. 숫자가 크면 사전 순으로 뒤인 것이다.

1. 맨 뒤부터 시작하여 처음 숫자가 감소하는 위치 idx1 을 찾는다. 

2. 다시 맨 뒤부터 시작하여 idx1 의 숫자보다 큰 숫자를 만나면 그 위치를 idx2 라고 한다.

3. idx1의 숫자와 idx2의 숫자의 자리를 바꾼다.

4. idx1 위치 이후의 숫자들을 오름차순 정렬한다.

 

그림으로 쉽게 살펴보자

 

처음 감소하는 위치 idx1 이후의 숫자들 '4 3 3 1' 은 내림차순 정렬이 되어있다. 이는 '3 2' 로 시작하여 만들 수 있는 단어의 가장 마지막 단어라는 것을 의미한다. 따라서 '3 2'로 만들 수 있는 단어는 끝났다. 사전 순 다음 단어를 구하기 위해선 2의 자리에 2 이후의 숫자들 중 2보다 큰 것 중 가장 작은 것이 와야한다. '4 3 3 1' 은 내림차순 정렬이 되어 있으므로 뒤에서부터 시작하여 2보다 처음으로 커지는 숫자의 위치가 idx2가 되며 해당 숫자가 2와 바꿀 대상이 된다. idx1의 숫자와 idx2의 숫자를 바꾼 후엔 idx1 위치 이후의 숫자들을 오름차순 정렬한다.

 

오름차순 정렬을 하면 '3 3' 으로 만들 수 있는 사전 순 가장 앞인 단어가 된다. 

 

코드

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

public class Main {

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

        for(int i=0; i<T; i++) {
            String word = br.readLine();
            char[] charArr = word.toCharArray();

            int len = charArr.length;
            int idx1 = -1;
            int idx2 = 0;
            // 처음 알파벳이 작아지는 (사전순 앞임을 의미) 위치
            for(int j=len-1; j>0; j--) {
                if(charArr[j-1] < charArr[j]) {
                     idx1 = j-1;
                     break;
                }
            }
            // 주어진 단어가 마지막 단어라면 그대로
            if(idx1 == -1) {
                System.out.println(word);
                continue;
            }

            // idx1 원소보다 큰 원소 찾기
            for(int j=len-1; j>idx1; j--) {
                if(charArr[idx1] < charArr[j]){
                    idx2 = j;
                    break;
                }
            }

            // 알파벳 위치 바꾸기
            char temp = charArr[idx2];
            charArr[idx2] = charArr[idx1];
            charArr[idx1] = temp;
            Arrays.sort(charArr, idx1+1, len); // 오름차순 정렬

            System.out.println(new String(charArr));
        }
    }
}