[코테] 리트코드 그리디 알고리즘 406. Queue Reconstruction by Height

406. Queue Reconstruction by Height

문제 링크

https://leetcode.com/problems/queue-reconstruction-by-height/description/

문제 설명

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

제한 사항

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.

입출력 예 #1

1. Input : people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
2. Output : [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
3. Explanation : Person 0 has height 5 with no other people taller or the same height in front.

Person 1 has height 7 with no other people taller or the same height in front.

Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.

Person 3 has height 6 with one person taller or the same height in front, which is person 1.

Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.

Person 5 has height 7 with one person taller or the same height in front, which is person 1.

Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

입출력 예 #2

1. Input : people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
2. Output : [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

문제 풀이

키가 크고, 앞에 있는 사람의 수가 작은 순으로 우선정렬 큐에 넣은 다음 하나씩 pop하여 앞에 있는 사람 수가 배열에 삽입하는 index가 되게 넣으면 된다.

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