16719_ZOAC

▶ 골드 5 (재귀)

풀이

처음에는 사전 순 알파벳을 순차적으로 출력하면 되는 문제인 줄 알았습니다.

 

하지만 무작정 순서대로 출력하는 것이 아니라,

사전 순에서 가장 빠른 알파벳을 찾고 출력한 후, 해당 인덱스 뒤의 범위의 문자열이 모두 출력될 때까지 동일한 과정을 진행합니다.

뒤 알파벳을 모두 출력하고 나면, 앞 범위의 문자열에 동일한 과정을 진행합니다.

 

이렇게 범위를 좁혀가면서 동일한 과정을 수행하는 것이기 때문에, 선택한 알파벳에 대해 뒷 범위, 앞 범위를 재귀로 진행합니다.

 

중요한 점은, 가장 빠른 알파벳을 찾을 때, 동일한 알파벳이 여러 개 있을 수 있기 때문에

현재 범위 내에서 for문을 통해 인덱스를 찾아줍니다.

또한, 뽑힌 알파벳의 인덱스는 따로 보관하여 출력할 때 써줍니다.

코드

# 16719 ZOAC
from collections import deque
import sys
input = sys.stdin.readline
str = input().strip()

num = []

def REC(start, end):
    if start > end:
        return

    mid = start
    for i in range(start, end + 1):
        if str[i] < str[mid]:
            mid = i

    num.append(mid)

    for i in range(len(str)):
        if i in num:
            print(str[i], end='')
    print()


    REC(mid + 1, end)
    REC(start, mid - 1)

REC(0, len(str) - 1)

# 가장 사전 순으로 먼저인 알파벳 먼저 출력하는데, 지금 인덱스보다 뒤쪽에 있어야함.
# 뒤쪽에 있는 인덱스를 다 출력했으면 앞쪽 꺼 출력