LeetCode 406. Queue Reconstruction by Height

파이썬 알고리즘 인터뷰 79번(리트코드 406번) Queue Reconstruction by Height
https://leetcode.com/problems/queue-reconstruction-by-height/

나의 풀이

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (x[0], -x[1]), reverse = True)
        result = [0] * len(people)

        while people:
            height, front = people.pop()
            idx = 0
            temp = front
            while temp > 0:
                if result[idx] == 0:
                    temp -= 1
                idx += 1
            while result[idx] != 0:
                idx += 1
            result[idx] = [height, front]
        
        return result

• 우선 주어진 배열을 키 기준 내림차순 정렬한다. 키가 같은 경우 2번째 인자는 오름차순으로 정렬.
• 그러면 배열을 .pop()하면 키가 작은 사람부터 나온다.
• 키가 가장 작은 사람의 정보가 [height, front]라면 front의 값이 비어있는 자리 중 그 사람의 위치이다. 그러니까 front=4이면 비어있는 자리 중 4번째 자리에 들어가면 된다.
• 다음으로 작은 사람을 불러와서 마찬가지로 비어있는 자리 중 자신의 front 번째 자리에 들어가면 된다.

다른 풀이1

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        output=[] 
        
        people.sort(key=lambda x: (-x[0], x[1]))                
        for a in people:
            output.insert(a[1], a)
        
        return output  

• insert메소드를 사용하는 것이 직접 자리를 찾는 것보다 빠르다.(빠른 C언어로 메소드가 구성되어 있다.)

다른 풀이2

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

        return result

배운 점

• 리스트의 메소드 중 insert는 써본 적이 없었는데 알아두어야겠다.