[백준]1138번: 한 줄로 서기

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

1138번: 한 줄로 서기

---

이 문제 풀 때 머리가 되게 안 돌아갔고 은근 어려웠다.

 

 

시간제한은 2초로 널널하고, 주어지는 N도 매우매우 작은 수이다.

이중포문 돌려서 하나씩 체크해도 전혀 문제되지 않겠다 생각해서 차근차근 풀어봄

 

아이디어

1. 크기가 n이고 전부 -1로 초기화되어있는 리스트 result를 만든다. (-1은 빈자리라는 의미)

2. 한 명씩 줄을 세운다.

  2-1. result 리스트를 순회하면서, 빈자리를 센다.(누군가 서있으면 자신보다 키가 작은 사람이므로 이 사람들은 빼고 센다)

  2-2. 빈자리 수가 자신보다 큰 사람 수와 같아지면, 바로 뒤 빈자리에 세운다.

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
arr=list(map(int,input().split()))

result=[-1]*n

for i in range(n):
  cnt=0
  for j in range(n):
    if result[j]==-1:
      if cnt>=arr[i]:
        result[j]=i+1
        break
      else:
        cnt+=1
 
for i in range(n):
  print(result[i],end=' ')