[알고리즘] 키에 따른 대기열 재구성

키에 따른 대기열 재구성

책 풀이

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

각각의 사람은 (h,k)의 두 정수 쌍을 갖는데, h는 그 사람의 키, k는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수를 뜻한다.우선순위 큐 자체가 매번 그때그때의 최소 또는 최댓값을 추출하기 때문에, 그리디에 자주 쓰인다.
우선 키 큰 사람들 순으로 그리고 k값이 작은 사람 순으로 뽑되, 뒤에 나오는 사람들은 인덱스로 삽입하면 된다.