[python] 1138번: 한 줄로 서기

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

1138번: 한 줄로 서기

 

풀이 방식

1번째 사람부터 N번째 사람까지 순서대로 자리를 채워넣는 식으로 진행한다.

 

6

2 3 0 0 1 0

 

일 경우 자리는 0 0 0 0 0 0, 총 6개의 자리다.

 

* 1번째 사람부터 계산

 

1: 2 -> 0 0 1 0 0 0

2: 3 -> 0 0 1 0 2 0

3: 0 -> 3 0 1 0 2 0

4: 0 -> 3 4 1 0 2 0

5: 1 -> 3 4 1 0 2 5

6: 0 -> 3 4 1 6 2 5

 

답: 341625

 

# 키가 i 일 때

 

1.  왼쪽에 나보다 큰사람이 0인 경우 -> 배열의 왼쪽부터 가장 먼저 만난 0의 자리에 i를 넣는다.

2. 왼쪽에 나보다 큰사람이 j명인 경우 -> 배열의 왼쪽부터 0 을 j만큼 지나친 이후의 0의 자리에 i를 넣는다.

 

위 2개의 방식을 반복문을 통해 처리하면, 위의 방식처럼 계산을 하며 적절한 답이 나온다.

 

from sys import stdin

N = int(input())

lines = [0]*(N+1)
arr = list(map(int,stdin.readline().split()))

cnt = 0
for i in range(N):
  if arr[i] == 0: # 왼쪽에 나보다 큰 사람이 없는 경우
    for j in range(1,N+1):
      if lines[j] == 0:
        lines[j] = i+1
        break
  else: # 왼쪽에 나보다 큰 사람이 arr[i] 명 만큼 있는 경우
    cnt = arr[i]
    for j in range(1,N+1):
      if lines[j] == 0 and cnt == 0:
        lines[j] = i+1
        break
      elif lines[j] == 0 and cnt != 0: # cnt 명 만큼의 자리를 지나쳐야 한다
        cnt -= 1
      else:
        continue

for j in range(1,N+1):
  print(lines[j],end=' ')