[BOJ] 16719. ZOAC(🥇, 구현)

문제

풀이

첨엔 단순히 알파벳 순서가 빠른거부터 차례대로 출력하면 되는 거라고 생각했는데 문자열이 사전 순으로 앞에 오도록 출력해야 되는 거였다.

1. 앞에서부터 순서가 가장 빠른 알파벳을 찾는다
2. 알파벳을 찾았으면 출력하고, 그 알파벳 다음 순서에 있는 단어들 중에서 가장 빠른 알파벳을 찾는다
3. 뒤에 더 이상 찾을 알파벳이 존재하지 않으면 앞으로 간다

빠른 알파벳을 찾고 그 다음부터 또 빠른 알파벳을 찾는 이유는, 사전순으로 문자를 나열하기 위해선 그 빠른 알파벳이 가장 앞에 있어야 하기 때문이다. 그래서 그 알파벳 뒤에 있는 문자들을 사전 순서대로 찾고, 그 다음에 정말 더 이상 찾을 수가 없다면 그 가장 빠른 알파벳 이전의 문자들을 찾는다.

일단 문자열 길이 만큼의 길이를 가지면서 빈 공백('')을 가지는 ans라는 리스트를 하나 만든다. 앞에서부터 알파벳을 찾고, 찾았으면 그 뒤부터 찾고, 이 방식을 재귀로 할 생각을 못하고 반복문으로 풀 생각을 했는데, left와 right로 나누어서 뒤에 더 찾을 문자가 있으면 right 함수를, 뒤에 더 찾을 게 없으면 left를 하려고 했는데 인덱스 처리가 너무 복잡했다.

문제 분류를 보니 재귀로 분류되어 있어서 재귀로 하는 방식을 다시 생각해봤다. 일단 젤 빠른 알파벳을 찾고, 찾았다면 출력하고 재귀로 그 다음 인덱스부터 젤 빠른 알파벳을 찾는다. 이걸 반복하다가 더 이상 1. 뒤에 문자가 존재하지 않거나, 2. 문자를 다 찾아서 더 찾을 문자가 없다면 return 한다. 그럼 첨으로 되돌아와서 거기서부터 젤 빠른 알파벳을 찾기 시작했던 그 인덱스로 되돌아와서 두 번째로 빠른 알파벳을 찾게 되고 위의 방법을 반복하게 된다.

STARTLINK를 예로 들면 A를 먼저 찾고, A 이후의 모든 문자들을 출력했다면 ARTLINK인 상태가 된다. A를 찾은 인덱스는 0부터 시작해서 찾은 것이므로(가장 처음에 찾았으니까) 더 이상 찾을 문자가 없으면 return 해서 시작 인덱스가 0인 상태로 되돌아오는 것이다. 그럼 다시 0부터 빠른 문자를 찾게 되는데 젤 빨랐던 A 이후의 문자는 이미 다 있기 때문에 그 너머까진 탐색하지 않고, 두 번째로 빠른 문자인 S를 찾게 된다.

난관

1. 근데 이 과정에서 idx = search(i+1)을 계속 idx = search(idx+1)로 해서 재귀가 무한대로 돌았다...
2. 알파벳을 찾았으면 출력을 하고 다음 함수로 넘어가야 하는데 함수로 넘어갔다가 출력을 하는바람에 순서가 엉망으로 나왔었다
3. 재귀 함수는 순서가 중요하다는 걸 깨달았다

# 40ms

string = input()
L = len(string)
ans = ['']*L

def search(i):
    global ans
    minOrd, idx = 150, -1
    for k in range(i, L):
        if ans[k] != '':
            return idx
        if ord(string[k]) < minOrd:
            minOrd = ord(string[k])
            idx = k
    return idx

def zoac(i):
    while True:
        idx = search(i+1)
        if idx == -1:
            return 
        ans[idx] = string[idx]
        print(''.join(ans))
        zoac(idx)
        
zoac(-1)

후기

재귀 너무 어렵다
문제 처음 보고 골드5급인가? 생각했는데 푸는데 이틀걸렸으니까 골드5 맞는듯