[BOJ] ZOAC - 16719 (G5)

시간 제한	메모리 제한
2 초	512 MB

문제

문자열을 하나씩 추가하면서 사전 순으로 가장 앞서는 문자열을 만들어 나가는 문제이다.

풀이

재귀적으로 가장 작은 문자를 찾아서 추가하는 문제이다.

코드

import sys

sys.setrecursionlimit(10**6)

string = sys.stdin.readline().strip()
length = len(string)

visited = [False] * length

def select_char(start, end):
    if start > end:
        return

    min_char = 'Z' + '1' 
    min_idx = -1
    for i in range(start, end + 1):
        if string[i] < min_char:
            min_char = string[i]
            min_idx = i

    visited[min_idx] = True

    current_result = ""
    for i in range(length):
        if visited[i]:
            current_result += string[i]
    print(current_result)
    select_char(min_idx + 1, end)
    select_char(start, min_idx - 1)

select_char(0, length - 1)

시간 복잡도

O(N^2)