이진 트리의 최대 깊이

난이도 | ★
리트코드 104.

문제

[eng]
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).

[kor]

여러 명의 사람들이 줄을 서 있다. 각각의 사람은 (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]]

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

• 설명
키가 5 인 사람이 가장 먼저 섰고, 앞에는 아무도 없다. 7 인 사람이 뒤따르고, 그보다 키가 더 큰 사람은 아무도 없다. 5 인 사람이 섰으며, 앞에 5, 7 두 명이 자신보다 크거나 같다. 6 인 사람의 앞에는 자신보다 큰 키 7 인 사람 한 명이 있다. 4 인 사람 앞에는 5, 7, 5, 6 네 명이 있다. 마지막으로 7 인 사람 앞에 자신보다 크거나 같은 이는 키가 7 인 사람 한 명이다

Constraints:

1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
It is guaranteed that the queue can be reconstructed.

[전제]

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        

문제 풀기 전 알고 갈 개념

• 큐
• greedy algorithm
• 우선순위 큐
• 힙정렬 Heap Sort

풀이과정

우선순위 큐를 이용한다
먼저, 위의 예시의 입출력인 대기열을 시각화 해보자

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

이 그림을 잘 살펴보면 일정한 패턴을 볼 수 있다
이 문제는 우선순위 큐를 이용하면 쉽게풀 수 있다.

• 우선순위 큐: 매번 그때그때의 최소 또는 최댓값을 추출
• 그리디에 어울리는 대표적인 자료구조
• ➡ 실제로 그리디 문제의 대부분은 우선순위 큐를 활용해 풀이함

우선순위 큐를 이용해 순서대로 예제 입력값을 추출해보면 다음과 같은 순서가 된다.

[[7,0]] (0번째 인덱스에 [7,0] 삽입)     
[[7,0],[7,1]] (1번째 인덱스에 [7,1] 삽입)        
[[7,0],[6,1],[7,1]] (1번째 인덱스에 [6,1] 삽입)       
[[5,0],[7,0],[6,1],[7,1]] (0번째 인덱스에 [5,0] 삽입)    
[[5,0],[7,0],[5,2],[6,1],[7,1]] (2번째 인덱스에 [5,2] 삽입)        
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] (4번째 인덱스에 [4,4] 삽입)        

[h, k]

• h: 큰 순서대로 추출되는 최대 힙 Max Heap 형태로 풀이 가능
• k: 삽입되는 인덱스로 활용 가능

힙정렬 Heap Sort을 이용해서 구현해보자.
파이썬의 heapq 모듈을 사용해보겠다!

h 최대힙 사용

h는 위의 예시에서와 같이 큰 순서대로 추출해야한다.

[PROBLEM]
파이썬은 최소 힙 Min Heap 만 지원함

✔ heapq.heappush(heap, item)
힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

[SOLUTION]
첫 번째 값을 음수로 변경해 최소 힙에서도 최대 힙처럼 구현하면 됨.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1

8
7
5
4
3
1

최대힙을 예제에 적용해보면,

    heap = [] # 키 역순, 인덱스 삽입 
    for person in people:
        heapq.heappush(heap, (-person[0], person[1]))

즉, heapq.heappush(heap, (-person[0], person[1]))) (우선 순위, 값)은

• (-person[0], person[1]): 우선순위가 [[-7,0],[-4,4],[-7,1],[-5,0],[-6,1],[-5,2]] 이므로 ➡ 이 중에서 h가 작은것부터 추출(-를 붙였으니 큰것부터 추출)
  • [[-7,0],[-7,1],[-6,1],[-5,0],[-5,2], [-4,4]]
• (-person[0], person[1]): 저 우선순위를 그래도 추출하는게 아닌 우선순위에 맞는 값을 heap = []에 저장한다.
  • [[-7,0],[-7,1],[-6,1],[-5,0],[-5,2], [-4,4]]

k 인덱스로 사용

두 번째 값을 인덱스로 해 삽입되는 위치로 구현가능.

✔ heapq.heappop(heap)
힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다.
힙이 비어 있으면, IndexError가 발생합니다.
팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.

result = [] # 키 역순, 인덱스 추출 
while heap:
    person = heapq.heappop(heap) 
    # insert(a, b)는 리스트의 a번째 위치에 b를 삽입하는 함수
    # 다시 -를 하니 +
    result.insert(person[1], [-person[0], person[1]]) 
print(result) 

[[7, 0]]
[[7, 0], [7, 1]]
[[7, 0], [6, 1], [7, 1]]
[[5, 0], [7, 0], [6, 1], [7, 1]]
[[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]
[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]    

전체 코드

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