9081번: 단어 맞추기

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

9081번: 단어 맞추기

언어 : Kotlin

 

문제 설명 :

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

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

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

 

입력 :

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

 

출력 :

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

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 1288MB

 

입출력 예 :

입력	출력
4 HELLO DRINK SHUTTLE ZOO	HELOL DRKIN SLEHTTU ZOO

 

풀이 : 

주어진 문자열들을 조합하여 기존 단어 바로 다음으로 올 문자열을 만들어야한다.

문제에서 주어진 예시 기준 BEER의 바로 다음은 BERE.

B	E	E	R
66	69	69	82
↓	↓	↓	↓
B	E	R	E
66	69	82	69

 

이를 아스키코드로 표핸해보면 위와 같이 나온다.

간단하게 봤을때 뒤에서부터 시작하여 뒷 인덱스에 있는 큰 문자를 앞 인덱스의 작은 문자와 맞바꾸는 것을 알 수 있다.

위 경우는 간단하게 한번 바꾸는 것으로 끝났으나 예를들어

 

D	R	I	N	K
68	82	73	78	75
↓	↓	↓	↓	↓
D	R	I	K	N
68	82	73	75	78

 

이 경우엔 뒤에 두 개 바꾼다고 끝나지 않는다.

기존 문자열보다 더 작아지기 때문에 사전순으로 했을때 기존 문자의 바로 뒤가 아니라 바로 앞에 오게 될 것이다.

D	R	I	K	N
68	82	73	75	78
↓	↓	↓	↓	↓
D	R	K	I	N
68	82	75	73	78

 

즉, 더 나아가 I와 바꾸고 그 뒤쪽을 사전순으로 정렬시켜 DRKIN이라는 문자열을 만들어야 기존 문자보다 크면서 만들 수 있는 문자열 중 가장 작은 문자열이 완성되어 사전순으로 했을때 바로 뒤에 오게 될 것이다.

 

1. 문자열의 오른쪽에서부터 선택한 문자 x에 대해 이 문자보다 오른쪽에 있는 문자 중 더 큰 값이 있는 것을 찾는다
2. x보다 오른쪽에 있고, x보다 큰 문자 중 가장 작은 문자를 찾아 위치를 바꾼다
3. 기존 x가 있던 위치를 i라고 했을 때, i를 기준으로 오른쪽에 있는 문자를 사전순으로 정렬시킨다

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    repeat(n) {
        val input = readLine().toCharArray()

        for (i in input.lastIndex - 1 downTo 0) {
            var bigChar = Pair(Int.MAX_VALUE, 0)

            for (j in i until input.size) {
                if (input[i] < input[j]) bigChar = Pair(bigChar.first.coerceAtMost(input[j].code), j)
            }

            if (bigChar.first != Int.MAX_VALUE) {
                input[i] = bigChar.first.toChar().also { input[bigChar.second] = input[i] }
                input.sort(i + 1, input.size)
                break
            }
        }

        bw.appendLine(input.joinToString(""))
    }
    bw.flush()
    bw.close()
}