[LeetCode] 406. Queue Reconstruction by Height

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

사람의 배열이 제공됩니다 (반드시 순서가 아님). 각 사람 [i] = [hi, ki]는 높이 hi의 i 번째 사람을 나타내며, 현재 사람 앞에 hi 이상의 높이를 가진 사람이 정확히 ki명이 있습니다. 입력 배열 people이 나타내는 큐를 재구성하고 반환합니다. 반환 된 대기열은 배열 대기열로 형식화되어야합니다. 여기서 queue [j] = [hj, kj]는 대기열에있는 j 번째 사람의 속성입니다 (queue [0]은 대기열의 맨 앞에있는 사람입니다).

✍️ 풀이

---

정렬을 사용해야 한다.

큰 숫자가 무조건 앞에 와야만 한다.
-> 큰 숫자부터 넣는다.

같은 숫자가 여러개이며 같은 숫자도 앞에 올 수 있다.
-> k가 작은 숫자를 먼저 넣어야 같은 숫자를 포함하면서 k조건을 만족할 수 있다.

따라서, 배열을 내림차순 정렬하되 숫자가 같다면 k를 기준으로 오름차순 정렬해야 한다.

정렬 후, 순서대로 꺼내면서 k번째 위치에 넣어주면 된다.

🛠 코드

---

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people = sorted(people, key=lambda x:(-x[0], x[1]))
            
        result = []
        for i in range(len(people)):
            h, k = people[i]
            result.insert(k, [h, k])
        return result
                

---

📝 정리

---

🎈 참고

---

Book 링크