백준 9081 단어 맞추기 Kotlin (그리디)

문제 출처 : 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을 넘지 않는다.

출력

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

알고리즘 분류

• 수학
• 구현
• 문자열
• 조합론

풀이

완전 탐색, 즉 순열로 모든 경우의 수를 구하는 것은 길이가 100이기 때문에 불가능하다.

따라서 dp, 그리디 등을 생각해볼 수 있는데, 그리디하게 풀 수 있다.

문제를 잘 파악하면 복잡한 알고리즘은 필요 없는 문제이다.

 

SHUTTLE을 예로 들면,

위 문자열을 아스키 코드로 변형하면 아래와 같다.

0	1	2	3	4	5	6
83	72	85	84	84	76	69

우리는 주어진 문자열의 문자들을 조합하여 사전 순으로 바로 다음에 오는 문자열을 찾아야 한다.

따라서 더 큰? 문자열을 만들되, 더 큰 문자열 중에 가장 작은 문자열이어야 한다.

직관적으로 1번 인덱스에 72 대신 72보다 큰 문자를  2~6번 인덱스에서 찾아서 바꿔야 하는 것이 보일 것이다.

그럼 더 큰 문자열은 만들었는데, 이중 가장 작은 문자열이어야 하므로 2~6번 인덱스를 정렬하면 작은 문자부터 앞으로 오기 때문에 이전 문자열 보다 더 큰 문자열이면서 가장 작은 문자열이 완성된다.

이를 정리하면 다음과 같다.

1. 문자열의 오른쪽에서부터 어떠한 문자 X에 대해 이 문자보다 오른쪽에 있는 문자들 중 더 큰 값이 있는 값을 찾는다.

2. X보다 오른쪽에 있으면서 X보다 더 큰 문자중, 가장 작은 문자를 찾아서 X와 swap한다.

3. 위에서 기존 X의 위치를 i라고 할 때, i의 오른쪽에 있는 문자들을 정렬한다. 

 

코드

val br = System.`in`.bufferedReader()
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()){
    //input
    val n = getInt()
    repeat(n){
        val input = br.readLine().toCharArray()
        for(i in input.size-2 downTo 0){
            var biggerCh = Pair(Int.MAX_VALUE,0)
            for(j in i until input.size){
                if(input[i]<input[j]){
                    biggerCh = Pair(biggerCh.first.coerceAtMost(input[j].code),j)
                }
            }
            //i 번째 문자보다 우측에 문자가 크다면 그 큰 값중 최솟값을 i위치에 넣기
            //이후 i 번째 뒤에 문자들을 정렬
            if(biggerCh.first!=Int.MAX_VALUE){
                input[i] = biggerCh.first.toChar().also { input[biggerCh.second] = input[i] }
                input.sort(i+1,input.size)
                break
            }
        }
        write("${String(input)}\n")
    }
    close()
}