백준 1138 한 줄로 서기

재귀함수를 만들어서 하나하나 옮바른 자리를 찾아가는 방법으로 풀이했다.
가능한 경우의 수도 1개뿐이고 N의 최대값도 10이었기에 RecursionError 없이 풀이 할 수 있었다.

📜 문제 바로 가기 : 한 줄로 서기

제출코드

import sys
input = sys.stdin.readline

N = int(input())
input_arr = list(map(int, input().split()))

arr = [] # (왼쪽에 나보다 큰 사람 수, 내 키=번호)
for i in range(N):
    arr.append((input_arr[i], i+1))

arr.sort() # 

lst = [0] * (N+1)
def recur(s, k, idx): # s 번째 사람 보고 있다.
    # s 보다 큰 사람을 k명 찾았고 idx 번째 부터 확인하면 된다.
    if s == N or lst[0] == 1: # s == N 이되면 완벽한 순서를 찾은것
        lst[0] = 1
        return
    
    if idx >= N+1:
        return
    
    cnt, num = arr[s]
    if k > cnt :
        return
    
    if k == cnt and lst[idx] == 0:
        lst[idx] = num
        recur(s+1, 0, 1)
        if lst[0] == 0:
            lst[idx] = 0

    
    if lst[idx] > num:
        recur(s, k+1, idx+1)
    elif lst[idx] == 0:
        recur(s, k+1, idx+1)
        recur(s, k, idx+1)
    else:
        recur(s, k, idx+1)

recur(0, 0, 1)
print(*lst[1:])

접근방법

왼쪽에 키큰 사람이 없는 것 부터 처리했다.
lst 배열에는 줄 서 있는 번호를 저장했으며 0번 인덱스 자리는 인덱스 번호도 맞출겸, 재귀함수 탈출용으로 만들겸 해서 비워두었다.

lst[idx] 가 '0' 이라는 것은 아직 그 자리가 비어있다는 뜻이다. 그러므로 그 자리에 키 큰 사람이 들어갈 경우와 키 작은 사람이 들어갈 경우 모두 재귀해야 한다.