[백준/파이썬] #16719

처음에 생각했던 풀이는 다음과 같다. 

string = input()
string_in_answer = [False] * len(string)
string_length = len(string)
smallest_alphabet = 1e9
smallest_alphabet_index = None
answer_indexes = []
weight = 0

for i in range(string_length):
    smallest_alphabet = 1e9
    smallest_alphabet_index = None
    weight = 0
    for j in range(string_length-1, -1, -1):
        if string_in_answer[j]:
            weight += 126
            continue
        if ord(string[j]) + weight < smallest_alphabet:
            smallest_alphabet = ord(string[j])
            smallest_alphabet_index = j
    string_in_answer[smallest_alphabet_index] = True
    answer_indexes.append(smallest_alphabet_index)

    answer_indexes.sort()
    answer = ""
    for answer_index in answer_indexes:
        answer += string[answer_index]
    print(answer)

 

30분 동안 푼 결과 성공하진 않았다. 나중에 찾아본 풀이를 보니 뒤에서부터 작은 알파벳을 찾아본다는 접근은 좋았다. 다만 재귀를 생각하지 못했어서 여러 테스트케이스를 못 맞춘 것 같다.

 

풀이를 이해하고 다시 푼 내용은 다음과 같다. 

string = input()

def fast_string(target_string, front_or_back, target_index):
    if target_string == "":
        return
    next_target_index = None
    fastest_string = min(target_string)
    fastest_index = target_string.index(fastest_string)
    if front_or_back == "front":
        result.insert(target_index, fastest_string)
        next_target_index = target_index
    elif front_or_back == "back":
        result.insert(target_index + 1, fastest_string)
        next_target_index = target_index + 1
    
    for r in result:
        print(r, end="")
    print()

    fast_string(target_string[fastest_index+1:], "back", next_target_index)
    fast_string(target_string[:fastest_index], "front", next_target_index)


result = []
fast_string(string, "front", 0)