[Python/파이썬] 백준 16719번 ZOAC

16719번: ZOAC

 

코드

import sys
sys.setrecursionlimit(10**6)

s = input()
order = [""]*len(s)


def recursion(arr, start):
    if not arr:
        return
    char = min(arr)
    idx = arr.index(char)

    order[start+idx] = char
    print(''.join(order))
    recursion(arr[idx+1:], start+idx+1)
    recursion(arr[:idx], start)


recursion(s, 0)

 

아직 보여지지 않은 문자 중 하나를 골라서 추가했을 때의 문자열이 사전순으로 앞에 오도록 하려면 당연히 가장 작은 알파벳을 고르면 된다. 그런데 이때 주의할 점은 이 알파벳들의 순서가 바뀌지는 않는다는 점이다. 그렇기 때문에 가장 작은 알파벳을 골랐다면 그 알파벳을 기준으로 오른쪽에서 앞서 진행했던 과정을 똑같이 재귀적으로 반복하여 문자열들을 뽑아내고, 오른쪽에서 모든 문자열을 뽑아낸 후에야 왼쪽으로 와서 진행해야 된다.

 

예를 들어, "STARTLINK"에서 가장 작은 문자는 A이다. 그럼 이제 이 A를 기준으로 오른쪽에 위치한 RTLINK에서 다시 가장 작은 문자를 찾는다. 그러면 I이고 또다시 RTL,NK로 나뉜 후 I의 오른쪽인 NK를 인자로 전달하여 함수를 재귀적으로 호출한다.  

 

이렇게 함수호출을 할 때마다 뽑힌 알파벳은 order 배열에 s 문자열에서의 원위치인 start+idx를 인덱스로 넣어준다. 그리고 order배열에 저장된 문자들을 join을 이용하여 출력해주면 되는데, 아직 뽑히지 않은 문자들은 "" 빈 칸이므로 당연히 출력 안된다.

 

 

 

어떻게 방식으로 풀어야하는지는 금방 생각났지만 구현이 어렵다...재귀 연습이 더 필요할 거 같다