79. Queue Reconstruction by Height

리트코드

• 여러 명의 사람들이 줄을 서 있다. 각각의 사람은 (h,k)의 두 정수 쌍을 갖는데,
  h는 그 사람의 키, k는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수를 뜻한다.

  이 값이 올바르도록 줄을 재정렬하는 알고리즘을 작성하라.

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]))
            
        result = []
        #키 역순, 인덱스 추출
        while heap:
            person = heapq.heappop(heap)
            #두번째 값을 인덱스로, 삽입위치 지정
            result.insert(person[1], [-person[0], person[1]])
        return result

• 먼저, 이 문제의 입출력인 대기열을 나타낸 그림을 보자.

  

  • 각각 자신보다 앞의 위치에 있는 키가 크거나 같은 사람의 숫자를 표현했다.

  • 이 그림을 잘 살펴보면 일정한 패턴이 엿보인다.

• 이 문제는 우선순위 큐를 이용하면 쉽게 풀 수 있다.

  • 우선순위 큐 자체가 매번 그때그때의 최소 혹은 최댓값을 추출하기 때문에, 그리디에 어울리는 대표적인 자료구조라 할 수 있다.

    • 그리디 문제의 대부분은 우선순위 큐를 활용해 풀이한다.

• 첫번째 값이 큰 순서대로 추출되는 최대 힙(Max Heap) 형태로 풀이할 수 있고, 두 번째 값은 삽입되는 인덱스로 활용할 수 있다.

  • 파이썬은 최소 힙(Min Heap)만 지원하기 때문에, 첫번째 값을 음수로 변경해 최소 힙에서도 최대 힙처럼 구현하면 될 것 같고

  • 두 번째 값을 인덱스로 해 삽입되는 위치로 구현할 수 있다.