# [Leetcode]406. Queue Reconstruction by Height

limelimejiwon·2022년 4월 13일
0

목록 보기
37/67

## 📄 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]))

for p in people:

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]))

while heap:
person=heapq.heappop(heap)
return answer

References