
▶ 골드 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)
# 가장 사전 순으로 먼저인 알파벳 먼저 출력하는데, 지금 인덱스보다 뒤쪽에 있어야함.
# 뒤쪽에 있는 인덱스를 다 출력했으면 앞쪽 꺼 출력
'Algorithm > Baekjoon' 카테고리의 다른 글
11123_양 한마리... 양 두마리... (0) | 2025.03.07 |
---|---|
15558_점프 게임 (0) | 2025.02.26 |
5014_스타트링크 (0) | 2025.02.25 |
16935_배열 돌리기3 (2) | 2025.02.24 |
11057_오르막수 (0) | 2025.02.24 |