[Python] 백준 16719 ZOAC (구현)

📌 문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

ZOAC

예제 출력 1

A
AC
OAC
ZOAC

예제 입력 2

BAC

예제 출력 2

A
AC
BAC

예제 입력 3

STARTLINK

예제 출력 3

A
AI
AIK
AINK
ALINK
ARLINK
ARTLINK
SARTLINK
STARTLINK

---

📌 풀이

💬 Code

import sys
input = sys.stdin.readline

n = list(input().rstrip()) # STEPBACK

# 입력이 한 글자면 그냥 그대로 출력해주고 종료
if len(n) == 1:
    print(n[0])
    sys.exit(0)

dic = []
for i in range(len(n)):
    dic.append((n[i], i))
dic = sorted(dic) # ABCEKPST

ans = [0 for _ in range(len(n))]
ans[dic[0][1]] = dic[0][0]

while dic:
    print(''.join([k for k in ans if k]))
    i = 1
    idx = 0
    isStart = 1

    while i < len(dic):
        add = ans.copy()
        add[dic[i][1]] = dic[i][0]

        if isStart:
            minimum = add
            isStart = 0
        elif ''.join([k for k in add if k]) < ''.join([k for k in minimum if k]):
            minimum = add
            idx = i
        i += 1

    ans = minimum
    del dic[idx]

💡 Solution

본래 문자열의 순서를 유지한 채 출력해야 하기 때문에 순서를 기억하기 위해 (문자, 인덱스)쌍이 담긴 리스트 dic을 생성했다.

• ans: 출력할 문자가 담긴 리스트
• add: ans에 한 문자씩 추가해본 리스트
• minimum: ans에 한 문자씩 추가해보면서 얻은 '가장 작은 문자열'이 담긴 리스트

• i: 한 문자씩 추가할 때 i번째 문자를 추가하는 것
• idx: '가장 작은 문자열'을 만든 문자를 가리키는 인덱스
• isStart: minimum은 계속 비교를 통해서 업데이트해줘야 하는데, 이번이 첫 반복문이라 아직 비교 대상이 없을 때를 나타내는 Flag

BACK이라는 입력이 들어왔다고 해보자.
while문(dic에 원소가 있는 동안 계속 반복)

• 1번째 while문
  • A 출력
  • BA, AC, AK 중 가장 작은 문자열인 AC 저장
  • 이 문자열을 만드는 데 사용된 C를 dic에서 삭제
• 2번째 while문
  • AC 출력
  • BAC, ACK 중 가장 작은 문자열인 ACK 저장
  • 이 문자열을 만드는 데 사용된 K를 dic에서 삭제
• 3번째 while문
  • ACK 출력
  • BACK 중 가장 작은 문자열인 BACK 저장
  • 이 문자열을 만드는 데 사용된 B를 dic에서 삭제
• 4번째 while문
  • BACK 출력
  • dic에 남아있는 A 삭제