[Python] 구현 - 1138.한줄로 서기(실2) / 뒤집어 insert

 

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

1138번: 한 줄로 서기

 

>>문제포인트

 

키가 큰 사람 순서대로 위치관계를 파악하는 것이 중요

 

예를 들어 키가 가장 작은 사람이

내 왼쪽에 나보다 키가 큰 사람이 1명 있어요! 라고 말한다면 그게 누구인지 모름

 

그러나 키가 두번째로 큰 사람이

내 왼쪽에 나보다 키가 큰 사람이 1명 있어요! 라고 말한다면 누구인지 특정이 됨

 

따라서, 키가 큰 사람부터 위치관계를 정하는 것이 쉬울 것이라 판단

 

=> 키가 큰 사람의 위치관계부터 파악해 list에 insert를 해주면 됨

 

ex)

사람의 수 : 4

각 위치관계 :  [2 1 1 0]

 

여기서 위치관계는 다음과 같음

 

키   왼쪽에 나보다 키가 큰 사람의 수

1     2

2     1

3     1

4     0

 

그러나 우린 키가 큰 사람부터 위치관계를 특정할 것이기 때문에

이 리스트를 뒤집어 판단

 

키   왼쪽에 나보다 키가 큰 사람의 수

4     0

3     1

2     1

1     2

 

이제 한명씩 위치관계를 파악하면 

키가 4인 사람 => 왼쪽에 키가 큰 사람이 아무도 없으므로 0번째에 넣기

키가 3인 사람 => 왼쪽에 키가 큰 사람이 1명 있으므로 1번째에 넣기

키가 2인 사람 => 왼쪽에 키가 큰 사람이 1명 있으므로 1번째에 넣기

키가 1인 사람 = > 왼쪽에 키가 큰 사람이 2명 있으므로 2번째에 넣기

 

이를 리스트로 보이면 다음과 같다.

answer	loc	height
[]	[0,1,1,2]	[4,3,2,1]
[4] => 키4를 0번째에 insert	[1,1,2]	[3,2,1]
[4,3] => 키 3을 1번째에 insert	[1,2]	[2.1]
[4,2,3] => 키 2를 1번째에 insert	[2]	[1]
[4,2,1.3] => 키 1을  2번째에 insert	[]	[]

 

>>코드

#키가 큰 순서대로 담기

n= int(input())

#사람들의 키
height = [i for i in range(1,n+1)]

#각 위치정보
loc = list(map(int, input().split()))
loc= loc[::-1]

#정답
answer=[]

#하나씩 받기
for i in loc:
  answer.insert(i,height.pop())

print(*answer)