[BOJ][Python] 1138 풀이

https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

n = int(input())
line = list(map(int, input().split()))
ans = [0 for _ in range(n)]
for i in range(len(line)): # 현재 선택된 친구
    cnt = 0
    for j in range(len(line)): # 바꿔가면서 비교중인 자리
        if ans[j] == 0 and cnt == line[i]:
            ans[j] = i+1
            break
        elif ans[j] > i+1 or ans[j] == 0:
            cnt += 1
print(*ans)

사실 엄청 간단하게 해결할 수 있는 문제였는데 시간을 좀 많이 썼습니다. 이번엔 너무 꼬아서 생각했는지 시키는대로 안하고 백트래킹으로 푸려고 재귀로 막 난리를 치다가 시간을 다 썼네요.

 

문제는 정말 하라는대로만 하면 됩니다. 작은 순서부터 배치를 하는게 굳이 조건문을 더 늘리지 않을 수 있기 때문에 작은 순서부터 필요한 공백만큼을 준 채로 자리에 집어넣습니다. 어차피 더 큰 숫자는 작은 숫자를 신경쓰지 않기 때문에 크거나 빈 자리인 경우에만 자리를 띄워주면 쉽게 해결이 가능한 문제입니다. 어째 최근에 계속 깔끔하게 문제를 못풀고 이리저리 허덕대는 느낌이네요.