백준 16719 ZOAC Kotlin (구현, next_permutation)

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

16719번: ZOAC

문제

2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.

앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!

규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.

예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.

바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.

입력

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

출력

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

알고리즘 분류

• 구현
• 문자열
• 재귀

풀이

요즘 구현 문제를 연습 중이다.

재귀를 이용해 풀었다.

분할 정복 기법을 이용한다.

현재 문자열에서 가장 사전 순으로 앞선 문자를 찾고, 그 문자를 적절한 위치에 넣어서 출력한다.

이때 CharArray를 이용하여 문자를 적절하게 위치시켰다.

그리고 사전순으로 앞선 문자의 위치를 기준점으로 삼아, 그 왼쪽 부분, 그 오른쪽 부분에 대해 재귀 함수를 호출한다.

STARTLINK를 예로 들면,

맨 처음엔 A가 기준이 되고, A를 출력한다.

STARTLINK

result : --A------

그 다음 사전 순으로 앞선 문자열을 뽑기 위해선,

A보다 뒤에 있는 문자(파란색 영역) 중에서 사전 순으로 가장 앞선 문자를 찾아야 한다.

그럼 다음 기준은 I가 되고, 이제 또 I보다 뒤에 있는 문자 중에서 사전 순으로 가장 앞선 문자를 찾는다.

STARTLINK
result : --A---I--

result : --A---I-K

K가 기준이 되고, K 뒤에는 문자가 없으니 다시 재귀를 거슬러 올라가면

K보다 앞에 있는 문자중에서 사전 순으로 찾아야 한다.

이 영역은 I와 K 사이이고, N밖에 없으니 N을 추가한다.

STARTLINK

result : --A---INK

이제 I의 오른쪽 부분은 탐색이 끝났으니 I의 왼쪽 영역을 탐색한다.

이 영역은 A와 I사이이다.

이런 식으로 현재 문자열에서 문자 하나를 뽑고, 그 문자를 기준으로 오른쪽 먼저 탐색, 왼쪽 탐색을 재귀적으로 호출하면 된다.

퀵 정렬의 동작 방식과 유사하다.

 

2022-06-26

몰랐는데 이게 c++의 next_permutation이었다.

그냥 구현했는데 알고보니 이게 자주 사용하는 알고리즘~?

2022.06.26 - [알고리즘 문제 풀이/백준] - 백준 10972 다음 순열 Kotlin (next_permutation)

2022.06.26 - [알고리즘 문제 풀이/백준] - 백준 10973 이전 순열 Kotlin (prev_permutation)

코드

val br = System.`in`.bufferedReader()

fun solve(str: String, result: CharArray, s: Int, e: Int){
    var minCh = 'Z'+1
    var minIdx = -1
    for(i in s until e){
        if(minCh > str[i]){
            minIdx = i
            minCh = str[i]
        }
    }
    if(minIdx!=-1){
        result[minIdx] = minCh
        //output
        for(i in result.indices) {
            print("${if (result[i].isLetter()) result[i] else ""}")
        }
        println()

        solve(str,result,minIdx+1,e)
        solve(str,result,s,minIdx)
    }

}

fun main(){
    //input, solve
    br.readLine().apply {
        solve(this, CharArray(length),0,length)
    }
}