[🥈2 / 백준 1138 / 파이썬] 한 줄로 서기

 

1138번: 한 줄로 서기

 

 

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

 

예제 입력 1 4 2 1 1 0	예제 출력 1 4 2 1 3
예제 입력 2 5 0 0 0 0 0	예제 출력 2 1 2 3 4 5
예제 입력 3 6 5 4 3 2 1 0	예제 출력 3 6 5 4 3 2 1
예제 입력 4 7 6 1 1 1 2 0 0	예제 출력 4 6 2 3 4 7 5 1

 

풀이

 

순서를 맞추기 위해 키 큰 사람의 수와 그 사람의 번호를 기록한다.

그리고 키 큰 사람의 수를 오름차순, 번호를 내림차순으로 정렬한다.

내림차순으로 정렬하는 이유는 정렬된 목록의 앞에서부터 추출하여 insert를 할 것이기 때문이다.

 

예제 4를 기준으로 위와 같이 진행하면 아래와 같은 튜플의 리스트가 만들어질 것이다.

 

(0, 7) (0, 6) (1, 4) (1, 3) (1, 2) (2, 5) (6, 1)

 

이제 앞에서부터 튜플을 뽑아가며 알고리즘을 진행한다.

앞은 자신보다 키 큰 사람의 수, 뒤는 해당 사람의 번호(키)이다.

편의상 각각 a, b로 칭한다.

 

이제 실제로 줄을 세울 배열인 ans라는 배열을 만든다.

ans 배열을 훑으며, 키보다 작은 사람이 있다면 카운트를 한다.

카운트가 a와 같아진다면, 해당 자리가 이 사람이 들어갈 자리가 된다.

 

import sys
input = sys.stdin.readline

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

for i in range(n):
    arr.append((nums[i],i+1))
arr.sort(key = lambda x : (x[0],-x[1]))

ans = []
for a,b in arr:
    cnt = 0
    for i in range(len(arr)):
        if a == cnt:
            ans.insert(i,b)
            break
        if ans[i] > b:
            cnt += 1
print(*arr)

 

단순 구현으로 풀었지만 스택, 혹은 브루트 포스로도 풀리는 문제라고도 한다.