리트코드 406번 Queue Reconstruction by Height (Python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (x[0], -x[1]))
        answer = []
        while people:
            p = people.pop()
            answer.insert(p[1], p)
        return answer

-h, k 순으로 뽑아서 결과 리스트에 k 위치에 넣으면 해결된다. 패턴을 찾는게 포인트인 문제이다.

다른 풀이

from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        heap = []
        for p in people:
            heapq.heappush(heap, (-p[0], p[1]))

        result = []
        while heap:
            h, k = heapq.heappop(heap)
            result.insert(k, [-h, k])
        return result

heap을 사용한 풀이이다. 성능에는 큰 차이 없지만 heap을 새롭게 할당하면서 메모리 사용량이 증가한다.

Reference

파이썬 알고리즘 인터뷰 79번