BOJ1138 한 줄로 서기

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

1138번: 한 줄로 서기

난이도: 실버2

소요시간:60+, hint

처음에는 쉬운 풀이법이 생각나지않아 생각난 방법으로 풀이를 하였는데 예외처리를 해야하는 부분이 많이 나와서 시간을 많이 잡아먹었으나 결국 풀지못하였다. 그래서 새로운 방법으로 풀었다. 한번 자리를 잡으면 뒤의 수는 나보다 크기때문에 왼쪽에만 칸을 비워두면 알아서 왼쪽수 조건이 충족된다는 것을 늦게 깨달았다,, 그 후 테스트를 몇번 돌리면서 잘못된 부분을 수정하고 제출하여 문제를 맞추었다.

 

 

 

키가 1인 사람부터 차례대로 세우면 된다.

주어진 입력에 따라서 자신보다 키가 큰 인원의 수만큼 왼쪽에 빈자리(list[i] ==0)를 놔두고 자리를 위치시키면 된다.

 

예를 들어 주어진 2 1 1 0 에 대해서는 1보다 키가 큰 사람이 왼쪽에 두 명이 있어야 하기 때문에 왼쪽에 빈자리를 두 개 두고 위치하면 된다.

0 0 1 0

위와 같이 배치가 될 것이다. 다음은 2인 사람을 배치한다고 한다면 2보다 왼쪽에 1자리만 놔두고 배치를 하면 된다.

0 2 1 0

위처럼 배치가 될 것이다. 3인 사람은 왼쪽에 한명이 자신보다 크기 때문에 한 자리를 놔두고 위치하면 되는데, 다른 자리들은 자리가 이미 있으므로 아래와 같이 배치된다.

0 2 1 3

 

 

#9:25 실버2

import sys

N=int(sys.stdin.readline())
inputList=list(map(int,sys.stdin.readline().split()))
resultList=[0 for _ in range(N)]

for i in range(N):
    left_p=inputList[i]
    left_count=0
    for j in range(N):
        if resultList[j]==0 and left_count==left_p:
            resultList[j]=i+1
            break
        elif resultList[j]==0:
            left_count+=1


print(*resultList)