BOJ 1138 - 한 줄로 서기

풀이

본인보다 큰 수가 왼쪽에 얼마나 있는 지 알려주는 정보를 받고 숫자를 순서대로 위치에 맞게 배정하는 문제이다.

2중 반복문을 통해 주어진 위치정보를 활용하여 1 부터 N 까지 숫자를 위치에 배정한다.

위치정보의 순서는 그 숫자의 순서이기 때문에 인덱스를 통해 ppl 이라는 배열에 하나씩 수정해주면된다.

예를 들어 1 이라는 숫자는 좌측에 자기보다 큰 숫자가 2개가 있음을 위치정보 배열을 통해 알 수 있을 때,

가장 큰 수인 N 이 N 개로 이루어진 ppl 이라는 배열을 통해 처음부터 자기보다 큰 수가 있을 경우 temp 를 수정해 temp 가 위치정보 배열의 숫자와 같아질 경우 그 위치에 1 이라는 숫자를 집어넣어주면된다.

이 과정을 N 번 반복하면 모든 숫자가 자기 위치에 배정될 수 있다.

이때 수정할 위치에 N 이 아닌 다른 숫자가 들어가 있다면 무시하고 N 을 찾아서 바꿔야한다.

소스코드

import sys
input = sys.stdin.readline
 
n = int(input())
inf = list(map(int, input().split()))
ppl = [n] * n
 
for i in range(n):
    temp = 0
    for j in range(n):
        if temp == inf[i] and ppl[j] == n:
            ppl[j] = i+1
            break
        elif ppl[j] > i+1:
            temp += 1
 
print(*ppl)

References

BOJ 1138 - 한 줄로 서기