[Leet code] 406. Queue Reconstruction by Height

Tag	그리디 알고리즘
Tags	heap
사이트	Leet code
이해	어느정도 이해
난이도	★★
메모	우선순위 큐와 그리디
발행 여부
최종 편집 일시	@2022년 1월 20일 오후 10:43
푼 날짜	@2022년 1월 20일 오후 10:15
Category	ps/그리디 알고리즘

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

풀이 코드 (책)

퇴고

문제 해설 및 주의사항

원문

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

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 <= hi <= 106

• 0 <= ki < people.length

• It is guaranteed that the queue can be reconstructed.

번역 및 주의사항

• people[i] = [h_i, k_i] 를 가진다. 정렬되어 있지는 않음.
  • [키, 앞에 자신의 키보다 크거나 같은 사람들의 수]

• 해당 people 배열을 정의에 맞게 재배열하자.

• Input:
  • [[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]]

---

풀이

우선순위 큐 자체가 그때그때의 최대 최소 값을 추출하기 때문에, 그리디에 어울리는 대표적인 자료구조이다. 실제로, 그리디의 대부분은 우선순위 큐를 활용해 풀이한다.

풀이 코드 (책)

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

• 예시를 보자.
  • [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    • heap 에 키(person[0]) 기준으로는 최대 힙, person[1] 에 대해서는 최소 힙으로 heappush 해보자.

      

    • 추출하는 과정을 따라가 보자. 힙은 항상 root 값 즉, 최대나 최소인 값만을 보장한다는 것을 기억해야 한다. 나머지의 정렬 상태를 보장해주지 않는다.

    

    

    • res 에 재 삽입하는 과정이 중요하다.
    • heap 에서는 항상 현재의 최댓값이 나오기 때문에, 그 이전에 res 에 삽입된 값은 항상 현재의 최댓값보다는 크거나 같다.
      • 그러므로, res 에 재삽입할 때,
      • 만약, person[1] 의 값이 3이라면
      • 3번째 index 에 삽입되어야 하는 것이다.
    • heappush 를 사용함으로써, person[1] 의 값을 삽입하는 index로써 사용할 수 있게 되는 것이다.

---

퇴고

• 힙이 정렬 상태를 보장해주지 않는다는 점

• 그리디에서는 주로 우선순위 큐를 사용한다는 점

• insert 를 활용한 풀이