[Leetcode]406. 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] = [$h_i$, $k_i$] represents the $i^{th}$ person of height $h_i$ with exactly $k_i$ other people in front who have a height greater than or equal to $h_i$.

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] = [$h_i$, $k_i$] is the attributes of the $j_th$ person in the queue (queue[0] is the person at the front of the queue).

여러 명의 사람들이 줄을 서 있다. 각각의 사람은 (h, k)의 두 정수 쌍을 갖는데, h는 그 사람의 키, k는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수를 뜻한다. 이 값이 올바르도록 줄을 재정렬하는 알고리즘을 작성하라.

Example 1:

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

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.

Example 2:

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

Constraints:

• 1 <= people.length <= 2000
• 0 <= $h_i$ <= 106
• 0 <= $k_i$ < people.length
• It is guaranteed that the queue can be reconstructed.

💻 My Submission

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        
        # sort people 
        people.sort(key=lambda x: (-x[0],x[1]))
        
        answer=[]
        for p in people:
            answer.insert(p[1],p)
        
        return answer

💡 What I learned - Heap(힙)

🚩 우선순위 큐(Priority) 이용하는 방법

우선순위 큐 자체가 매번 그때 그때의 최솟값 or 최댓값을 추출하므로, Greedy에 어울리는 대표적인 자료구조라 할 수 있다.

나의 풀이 방법와 유사하다.

• 첫 번째 값: 큰 순서대로 추출되는 최대 힙(Max Heap)
• 두 번째 값: 삽입되는 인덱스

파이썬은 최소 힙(Min Heap)만 지원하므로, 첫 번째 값을 음수로 변경해 구현하면 되고, 두 번째 값을 인덱스로 해 삽입되는 위치로 구현할 수 있다.

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        
        heap=[]
        for p in people:
            heapq.heappush(heap, (-p[0],p[1]))
        
        answer=[]
        while heap:
            person=heapq.heappop(heap)
            answer.insert(person[1],[-person[0],person[1],])
        return answer

References

• https://leetcode.com/problems/queue-reconstruction-by-height/
• 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트 - 파이썬 알고리즘 인터뷰 (박상길 지음)