[알고리즘] ZOAC python(백준_16719)

문제

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

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

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

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

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

입력

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

출력

 

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

https://www.acmicpc.net/problem/16719

 

 

문제 풀이 과정

이 문제는 특정 문자열을 사전순으로 가장 앞에 오게끔 점차적으로 조합해가며 보여주는 과정을 구현하는 것입니다. 이 규칙에 따라 가장 앞에 오도록 보여주기 위해, 매 단계에서 아직 표시하지 않은 문자 중에서 사전순으로 가장 빠른 문자를 선택하여 위치시키고, 이를 반복하는 구조를 만들어야 합니다.

1. 기본 설정 및 초기화
   • targetString에서 입력 문자열을 받습니다.
   • visited 리스트는 현재까지 표시된 문자를 저장하는 역할을 하며, 문자열의 길이와 같은 크기로 빈 문자열로 초기화됩니다.
   • res는 각 단계별 결과 문자열을 저장하여 나중에 출력하는 데 사용됩니다.
2. 재귀 함수 find 동작 설명
   • 함수 find는 입력으로 startInd(시작 인덱스)와 prevString(이전 단계에서 아직 표시하지 않은 문자열 부분)을 받습니다.
   • prevString이 비어 있지 않을 때까지 재귀적으로 호출되어 남은 문자에서 가장 작은 문자를 찾아 이를 visited에 추가하는 과정을 반복합니다.
3. 가장 작은 문자와 그 인덱스 찾기
   • prevString에서 가장 작은 문자를 minVal로 저장하고, 이 문자의 minIndex를 계산합니다.
   • minIndex는 현재 startInd에 더해져 visited의 올바른 위치에 해당 문자를 배치합니다.
   • 이렇게 visited 리스트를 통해 단계별로 점점 더 많은 문자가 표시되는 과정을 거쳐 res 리스트에 저장됩니다.
4. 다음 재귀 호출
   • 재귀 호출은 prevString을 minIndex를 기준으로 양분하여 수행됩니다:
     • find(startInd + minIndex + 1, prevString[minIndex + 1:])는 minVal 뒤에 남아있는 문자열에 대해 재귀 호출을 실행합니다.
     • find(startInd, prevString[: minIndex])는 minVal 앞에 남아있는 문자열에 대해 재귀 호출을 실행하여 그 다음 가장 작은 문자를 찾는 과정을 반복합니다.
   • 이 과정으로 현재 문자열을 사전순으로 가장 앞에 오게 하는 조합을 찾아가게 됩니다.
5. 결과 출력
   • 모든 재귀 호출이 종료된 후, res 리스트에 담긴 단계별 문자열을 한 줄씩 출력하여 각 과정을 표현합니다.

import sys
input = sys.stdin.readline

targetString = input().strip()
res = []
visited = [""] * len(targetString)
def find(startInd, prevString) :
    if not prevString:
        return
    minVal = min(prevString)
    minIndex = prevString.index(minVal)
    visited[minIndex + startInd] = minVal
    res.append("".join(visited))
    find(startInd + minIndex + 1, prevString[minIndex + 1:])
    find(startInd, prevString[: minIndex])
    
find(0, targetString)
print("\n".join(res))