여러 명의 사람들이 줄을 서 있다. 각각의 사람은 (h,k)
의 두 정수 쌍을 갖는데,
h
는 그 사람의 키, k
는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수를 뜻한다.
이 값이 올바르도록 줄을 재정렬하는 알고리즘을 작성하라.
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
heap = []
#키 역순, 인덱스 삽입
for person in people:
heapq.heappush(heap, (-person[0], person[1]))
result = []
#키 역순, 인덱스 추출
while heap:
person = heapq.heappop(heap)
#두번째 값을 인덱스로, 삽입위치 지정
result.insert(person[1], [-person[0], person[1]])
return result
먼저, 이 문제의 입출력인 대기열을 나타낸 그림을 보자.
각각 자신보다 앞의 위치에 있는 키가 크거나 같은 사람의 숫자를 표현했다.
이 그림을 잘 살펴보면 일정한 패턴이 엿보인다.
이 문제는 우선순위 큐를 이용하면 쉽게 풀 수 있다.
우선순위 큐 자체가 매번 그때그때의 최소 혹은 최댓값을 추출하기 때문에, 그리디에 어울리는 대표적인 자료구조라 할 수 있다.
첫번째 값이 큰 순서대로 추출되는 최대 힙(Max Heap) 형태로 풀이할 수 있고, 두 번째 값은 삽입되는 인덱스로 활용할 수 있다.
파이썬은 최소 힙(Min Heap)만 지원하기 때문에, 첫번째 값을 음수로 변경해 최소 힙에서도 최대 힙처럼 구현하면 될 것 같고
두 번째 값을 인덱스로 해 삽입되는 위치로 구현할 수 있다.