https://leetcode.com/problems/queue-reconstruction-by-height/

 

Queue Reconstruction by Height - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

<문제>

여러 명의 사람들이 줄을 서 있다. 각각의 사람은 [h, k] 정수 쌍을 갖는데,
h은 사람의 키, k는 앞의 사람들 중 자신의 키 이상인 사람들의 수를 의미한다.
줄 서 있는 사람들의 순서대로 정렬해보아라.

 

<예시>

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Explanation:

Person 0 has height 5 with no other people taller or the same height in front.

Person 1 has height 7 with no other people taller or the same height in front.

Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.

Person 3 has height 6 with one person taller or the same height in front, which is person 1.

Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.

Person 5 has height 7 with one person taller or the same height in front, which is person 1.

Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

 


'''
406. Queue Reconstruction by Height
https://leetcode.com/problems/queue-reconstruction-by-height/
여러 명의 사람들이 줄을 서 있다. 각각의 사람은 [h, k] 정수 쌍을 갖는데,
h은 사람의 키, k는 앞의 사람들 중 자신의 키 이상인 사람들의 수를 의미한다.
줄 서 있는 사람들의 순서대로 정렬해보아라.
'''
class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """

        # max heap -> greedy alorithm에서 heap 사용빈도 높다
        heap = []
        for p in people:
            heapq.heappush(heap, (-p[0], p[1]))

        result = []
        while heap:
            p = heapq.heappop(heap)
            result.insert(p[1], [-p[0], p[1]])

        return result

 

그리디 알고리즘에서 우선순위 큐를 많이 사용한다고 한다.

위의 풀이는 너무 신기해서 .. 

값을 max heap에 넣어서 정렬한 뒤, 큰 값부터 꺼내며 정렬해 나간다는 것이 신기했다.

내가 이 풀이를 떠올릴 수 있을까?

+ Recent posts