1138. 한줄서기

1138 문제 보기

Difficulty : Silver 2

Status : Failed

Time : 00:11:39

접근 방식

아무런 해결책도 생각나지를 않았어오...^.^
구현문제인데, 왼쪽에 본인보다 큰 값이 몇개 있는지의 데이터를 이용하긴 했지만,
왼쪽 데이터들 사이에서 대소관계를 비교해 위치시키는 방법을 생각하기가 어려웠다.
그래서 정답을 봐버렸다 ㅎㅁㅎ

최종 코드

import sys
input = sys.stdin.readline

N = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))
ans = [0] * N

for i in range(N):
  cnt = 0
  for j in range(N):
    if cnt == arr[i] and ans[j] == 0:
      ans[j] = i + 1
      break
    elif ans[j] == 0:
      cnt += 1

print(*ans)

문제의 입력값을 뜯어보자면,
0~N-1의 인덱스를 1~N으로 생각하고, 이를 그 사람의 키로 봐야한다.
각 인덱스(1~N)에 주어지는 input 값은 왼쪽에 위치하는 키가 더 큰 사람의 수다.

예제 입력 1을 통해 코드를 설명하자면,

4
2 1 1 0

에서 각 숫자를 왼쪽에 있는 사람 수로 생각하며 아래와 같이 값을 채워간다.

0 0 1 0
0 2 1 0 
0 2 1 3
4 2 1 3

키는 1~N에 해당하므로 앞의 값이 0인 경우에는 cnt의 값을 올려준다.
ans[j]값이 0인 동시에 cnt의 값이 앞에 필요한 사람 수와 같아지는 경우에 해당 값을 ans[j]에 넣어주고 반복문을 빠져나간다.