백준 1138 한 줄로 서기 Python

🐸 문제 정보

1138번: 한 줄로 서기

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

18.31m

 

📝 풀이

쉬운 구현 문제였다.

뒤에서부터 순회하면서 아래 조건대로 정답 리스트에 (인덱스 + 1)을 추가해주면 되는 문제였다.

1. 왼쪽에 나보다 큰 사람이 없다면, 정답 리스트 가장 왼쪽에 (인덱스 + 1) 추가
2. 왼쪽에 나보다 큰 사람이 있지만, 내 순서가 정답 리스트의 길이보다 작다면, 내 순서가 될 자리에 (인덱스 + 1) 추가
3. 왼쪽에 나보다 큰 사람밖에 없다면, 정답 리스트 가장 오른쪽에 (인덱스 + 1) 추가

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
res = []

for i in range(n - 1, -1, -1):
    length = len(res)
    if nums[i] == 0:
        res = [i + 1] + res
    elif nums[i] < length:
        res = res[:nums[i]] + [i + 1] + res[nums[i]:]
    else:
        res.append(i + 1)

print(*res)