406. Queue Reconstruction by Height

입력은 people = [[h1, k1], [h2, k2], [h3, k3]...]

h는 해당 사람의 키, k는 자기 앞에 사람들 중 자신의 키 이상인 사람들의 수를 나타낸다.

입력은 이 조건대로가 아닌 랜덤으로 들어가 있다.

따라서 출력은 이 배열이 올바른 순서대로 재정렬된 결과를 나타낸다.

이 배열이 올바른 순서대로 재정렬하는 알고리즘을 만들어라

 

---

풀이

1. 가장 큰 사람일 수록 앞에 사람이 없기 때문에 가장 큰 사람일수록 앞에 배치를 한다.

2. 그리고 같은 사람일 경우 k가 작은 순으로 앞에 배치한다.

 

그러면 앞에 키 크고 동일할 경우 k가 적은 순서대로 나온다.

 

이런 우선순위를 사용하기 위해 heapq 우선순위 큐를 이용하여 큐에 삽입한다.

그 이후에 pop을 할 때마다 가장 크고 k가 작은 순으로 뽑힌다.

k는 index로 생각하여 새로운 결과값에 넣으면 된다.

 

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

 

참고로 heapq는 최소힙만 지원하기 때문에 person[0]을 음수값으로 변경하여 최대힙으로 사용하였다.