문제 접근
문제
2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.
앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!
규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.
예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.
바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.
주의할 점
주의할 점은 추가할 문자 하나를 사전 순으로 보는 것이 아니라, 전체 문자열을 사전순으로 봐야한다는 것이다.
예제 2에서 BAC를 표현해야 한다.
문자 하나를 사전 순으로 본다면 결과는
A
BA
BAC
가 되어야 한다. 하지만 예제 결과를 보면 아래와 같다.
A
AC
BAC
따라서 추가했을 때 문자열이 사전 순으로 앞서는 경우로 생각해야 한다.
문제 해결을 위한 생각
그렇다면 어떻게 문자도 아니고 문자열을 사전 순으로 앞서게 표현하면서 결과에 사이사이에 문자들을 추가할 수 있을까?
STARTLINK 예시를 보자
STARTLINK에서 A가 가장 빠른 문자이다. 하나를 추가했을 때 가장 빠른 문자열이 되기 위해서는 A가 가장 앞에 오고 A의 뒤에 있는 문자들 중 가장 빠른 문자가 와야한다.
이를 위해서 A를 기준으로 두개의 리스트로 슬라이싱하고 뒤의 리스트에서 가장 빠른 문자를 찾아 결과 리스트에 추가해주는 방법을 사용한다.
이렇게 되면 가장 빠른 문자가 뒤의 리스트를 전부 추가할 때 까지 앞에 있게 되면서 자연스럽게 가장 빠른 문자열이 되는 것이다.
문제 풀이
재귀
자세한 내용은 코드 주석을 보면서 확인하도록 하쟈
결국 전체 흐름을 설명하자면
1. 전체 문자열을 받음
2. 문자열 중 가장 빠른 문자를 선택하여 결과 리스트에 넣기
3. 그 문자를 기준으로 슬라이싱하여 뒤에 있는 리스트에 같은 내용을 반복
4. 뒤에 있는 리스트가 끝나면 앞에 있는 리스트에 같은 내용 반복
5. 끗~
# 최소 문자를 확인할 리스트 = part_string
# 이 리스트가 최소 문자를 기준으로 앞에 있는지 뒤에 있는지를 확인할 매개변수 = f_or_b
# 결과 리스트에 어디에 최소 문자를 추가해야 하는지를 알려줄 변수 = before_index
def fast_string(part_string, f_or_b, before_index):
if len(part_string)<=0: # 재귀 종료 조건
return
fast_chr = min(part_string) # 부분 문자열에서 가장 빠른 문자
index = part_string.index(fast_chr) # 그 문자의 index
if f_or_b=='b': # next_index는 결과 문자열 리스트에서 어디에 추가해야 하는지를 넘겨주는 변수이다.
result.insert(before_index+1, fast_chr)
next_index = before_index + 1
elif f_or_b == 'f':
result.insert(before_index, fast_chr)
next_index = before_index
for i in result: # 결과 출력 (하나 추가할 때 마다 출력해줘야 되기 때문에 여기 넣음)
print(i, end='')
print()
fast_string(part_string[index+1:], 'b', next_index) # 뒤
fast_string(part_string[:index],'f', next_index) # 앞
# 문자열 중 사전 순으로 가장 빠른 문자를 찾고 그 뒤를 끝낸 뒤에 앞을 끝내기제출 코드
import sys
string = list(str(sys.stdin.readline().rstrip()))
def fast_string(part_string, f_or_b, before_index):
if len(part_string)<=0:
return
fast_chr = min(part_string)
index = part_string.index(fast_chr)
if f_or_b=='b':
result.insert(before_index+1, fast_chr)
next_index = before_index + 1
elif f_or_b == 'f':
result.insert(before_index, fast_chr)
next_index = before_index
for i in result:
print(i, end='')
print()
fast_string(part_string[index+1:], 'b', next_index) # 뒤
fast_string(part_string[:index],'f', next_index) # 앞
# 문자열 중 사전 순으로 가장 빠른 문자를 찾고 그 뒤를 끝낸 뒤에 앞을 끝내기
result = []
fast_string(string,'f',0)
