2022.03.08 73일차

백준 9081번 (단어 맞추기)

문제

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

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

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

나의 풀이

1. 주어진 단어의 다음 단어 출력, 마지막이면 그대로 출력
2. 조건 - 일의 자리부터 확인, 앞에 자기보다 작은 수 있으면 조건 충족
3. 반복문이 끝날때까지 자기보다 작은 수가 없으면 조건 불충족
4. index를 활용해서 조건 파악
5. 조건 충족할 때 위치 교체
6. 바꾸는 위치에서 앞쪽 이후 단어들은 오름차순 정렬

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));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            char[] tempArr = br.readLine().toCharArray();

            int index1 = -1;
            int index2 = 0;

            for (int x = tempArr.length - 1; x > 0; x--) {
                if (tempArr[x - 1] < tempArr[x]) {
                    index1 = x - 1;
                    break;
                }
            }

            if (index1 == -1) {
                for (char c : tempArr) {
                    sb.append(c);
                }
                sb.append("\n");
            } else {
                for (int z = tempArr.length - 1; z >= 0; z--) {
                    if (tempArr[index1] < tempArr[z]) {
                        index2 = z;
                        break;
                    }
                }

                char temp = tempArr[index1];
                tempArr[index1] = tempArr[index2];
                tempArr[index2] = temp;

                Arrays.sort(tempArr, index1 + 1, tempArr.length);

                for (char c : tempArr) {
                    sb.append(c);
                }
                sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}

생각하기