[Java] 백준 9081번 : 단어 맞추기

문제

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

9081번: 단어 맞추기

 

 

풀이 과정

주어진 문자열을 숫자로 나타내면 다음과 같이 볼 수 있다.

abcde fghij klmno pqrst uvwxy z
HELLO = 8 5 12 12 15
DRINK = 4 18 9 14 11
SHUTTLE = 19 8 21 20 20 12 5

여기서 다음 수를 구할 때는, 뒤에서 부터 봤을 때 오름차순으로 올라가다가 꺾이는 지점의 수(top) 이전 값과 그 이후의 숫자 중 다음으로 큰 값과 교체한다. 그리고나서 top 이후의 숫자들 모두 오름차순 정렬을 하면 된다.

 

예를 들어 SHUTTLE 같은 경우, 꺾이는 지점은 8이고 8 이후의 숫자 중에서 8 다음으로 큰 숫자는 12이다. top이후의 숫자는 내림차순으로 되어있기 때문에 앞&뒤를 swap해가면서 오름차순 정렬을 빠르게 하면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        while(T-- > 0){
            char[] input = br.readLine().toCharArray();
            int lastIdx = input.length - 1;
            //1. 꼭대기 구하기
            int top = lastIdx;
            while(top > 0 && input[top - 1] >= input[top]){
                top--;
            }

            if(top > 0){
                //2. 꼭대기랑 swap할 큰값고르기
                int pos = lastIdx;
                while(input[top-1] >= input[pos]) pos--;

                //3. swap하고, 오름차순 정렬하기
                swap(input, top-1, pos);
                while(top < lastIdx){
                    swap(input, top, lastIdx);
                    top++;
                    lastIdx--;
                }
            }

            for(char c : input){
                sb.append(c);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static void swap(char[] input, int i, int j){
        char temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }


}

 

 

결과