[LeetCode] 406 | Queue Reconstruction by Height | Python

---

문제 링크: https://leetcode.com/problems/queue-reconstruction-by-height/

---

문제

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 $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_j$, $k_j$] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

---

조건

• 1 <= people.length <= 2000
• 0 <= $h_i$ <= $10^6$
• 0 <= $k_i$ < people.length
• It is guaranteed that the queue can be reconstructed.

---

내 풀이

사람을 키가 작은 순으로 정렬한다.

정답으로 리턴할 ans의 원소를 [h, k]라 할 때, h를 max로 둔다.

현재 사람을 [h, k]라 할 때, 앞에 k명 만큼 큰 사람을 두는 pos를 찾는다.(첫번째 while 문)

해당하는 pos를 찾으면 ans에 비어있는 자리를 찾아서 넣는다.(두번째 while 문)

---

코드

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort()
        ans = [[1000001, -1] for _ in range(len(people))]
        
        for h, k in people:
            num_taller, pos = 0, 0
            
            while num_taller < k:
                if ans[pos][0] >= h:
                    num_taller += 1
                pos += 1
                
            while ans[pos][1] != -1:
                pos += 1
            ans[pos] = [h, k]
            
        return ans