16719번: ZOAC

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

16719번: ZOAC

언어 : Kotlin

 

문제 설명 :

2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.
앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!
규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.

예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.
바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.

 

입력 :

첫 번째 줄에 알파벳 대문자로 구성된 문자열이 주어진다. 문자열의 길이는 최대 100자이다.

 

출력 :

규칙에 맞게 순서대로 문자열을 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
ZOAC	A AC OAC ZOAC
BAC	A AC BAC
STARTLINK	A AI AIK AINK ALINK ARLINK ARTLINK SARTLINK STARTLINK

 

풀이 : 

C++에 존재하는 next_permutation을 kotlin으로 구현하면 풀린다.

next_permutation의 과정은 다음과 같다.

1. 오른쪽부터 왼쪽으로 바꿀 위치 i를 찾는다.
2. 이 i는 i의 오른쪽 요소들 중 i보다 큰 값이 있는 경우 i가 성립된다.
3. i의 오른쪽에 i보다 큰 값이 있다면, 이 큰 값 중 가장 작은 값과 swap한다.
4. i에는 가장 작은 값이 들어와 있으므로, i의 우측 요소들을 오름차순 정렬해준다.

next_permutation 이미지 설명

 

좀 더 자세히 알고 싶다면?

https://medium.com/depayse/kotlin-%EC%88%9C%EC%97%B4-permutation-36e85898896c

[Kotlin] 순열(Permutation)

 

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

val bw = BufferedWriter(OutputStreamWriter(System.out))

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {


    readLine().apply {
        nextPermutation(this, CharArray(length), 0, length)
    }

    bw.flush()
    bw.close()
}

fun nextPermutation(input: String, output: CharArray, start: Int, end: Int) {
    var minChar = 'Z' + 1
    var minIndex = -1

    for (i in start until end) {
        if (minChar > input[i]) {
            minChar = input[i]
            minIndex = i
        }
    }

    if (minIndex != -1) {
        output[minIndex] = minChar

        for (i in output.indices) {
            bw.write("${if (output[i].isLetter()) output[i] else ""}")
        }
        bw.appendLine()

        nextPermutation(input, output, minIndex + 1, end)
        nextPermutation(input, output, start, minIndex)
    }
}