백준 9081 단어 맞추기(Java)

문제 출처 : https://www.acmicpc.net/problem/9081

9081번: 단어 맞추기

문제 설명

BEER라는 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬하게 되면

BEER
BERE
BREE
EBER
EBRE
EEBR
EERB
ERBE
EREB
RBEE
REBE
REEB

와 같이 된다. 이러한 순서에서 BEER 다음에 오는 단어는 BERE가 된다. 이와 같이 단어를 주면 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알파벳으로 이루어진다. 단어의 길이는 100을 넘지 않는다.

출력

각 테스트 케이스에 대해서 주어진 단어 바로 다음에 나타나는 단어를 한 줄에 하나씩 출력하시오. 만일 주어진 단어가 마지막 단어이라면 그냥 주어진 단어를 출력한다.

풀이

처음엔 모든 조합을 구하고 해당 문자 다음 index를 출력하는 방식으로 구현했는데 시간 초과가 나서 기준 문자열에서만 비교해서 다음 문자가 올 값을 정하는 방식으로 생각하였다.

찾은 규칙으로는 뒤에서부터 탐색하여 오름차순이 깨지는 구간에서의 min값과 minIdx를 찾는다.

(찾지 못할 경우에는 마지막 단어이기 때문에 그대로 출력해준다.)

다시 뒤에서부터 min값보다 큰 값 max를 찾고 min과 max의 값을 바꿔주고 min부터 마지막까지 정렬을 해주면된다.

코드

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

public class boj_9081 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        for (int t = 0; t < N; t++) {
            String str = br.readLine();
            int length = str.length();
            char[] word = new char[length];

            for (int i = 0; i < length; i++) {
                word[i] = str.charAt(i);
            }

            int min = 0;
            int minIdx = -1;
            int maxIdx = 0;
            loop:for (int i = length - 1; i > 0; i--) {
                if (word[i] > word[i - 1]) {
                    min = word[i - 1];
                    minIdx = i - 1;
                    break loop;
                }
            }

            if (minIdx == -1) {
                sb.append(str).append("\n");
            } else {
                for (int i = length - 1; i >= 0; i--) {
                    if (word[i] > min) {
                        maxIdx = i;
                        break;
                    }
                }

                char temp = word[minIdx];
                word[minIdx] = word[maxIdx];
                word[maxIdx] = temp;

                Arrays.sort(word, minIdx + 1, length);

                for (char result : word) {
                    sb.append(result);
                }
                sb.append("\n");
            }


        }
        System.out.println(sb);
    }
}

결과