[백준 16719] ZOAC (python)

16719번: ZOAC

---

재귀를 통해 작은 알파벳을 선택한다.

 

1. 정답을 출력할 result 배열을 만든다.
2. arr에서 제일 작은 알파벳을 찾는다.
3. 해당 알파벳을 기준으로 뒷배열에서 또 작업을 한 뒤, 앞배열에서 작업을 한다.

 

import sys
input = sys.stdin.readline

S = list(input().rstrip())
result = ['']*len(S)


def func(arr, start):
    if not arr:
        return
    _min = min(arr)
    idx = arr.index(_min)
    result[start+idx] = _min
    print("".join(result))
    func(arr[idx+1:], start+idx+1)
    func(arr[:idx], start)


func(S, 0)