[그리디 알고리즘] 키에 따른 대기열 재구성

406 | Queue Reconstruction by Height
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] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

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

 

Example 1:

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.

Example 2:

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

 

Constraints:

• 1 <= people.length <= 2000
• 0 <= hi <= 106
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.

 

 

 

작성 코드

 

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        queue = []
        people.sort(key = lambda x : (x[0], -x[1]))
        people_len = len(people)
        for p in range(people_len):
            temp = people.pop()          
            idx = 0
            while queue and temp[1] > idx:
                idx += 1
            queue.insert(idx, temp)
        return queue

 

• x[0](키) 오름차순 정렬 후 x[1] 내림차순 정렬
• people 에서 pop 하면서 temp 에 붙임
• queue에 원소가 있고 temp[1] (앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수) 가 idx 보다 크다면 idx 계속 돌기
• idx 가 temp[1] 크거나 같아진 순간 종료
• idx 위치에 temp 삽입

 

 

참고 코드

 

 

import heapq
from typing import List


class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        heap = []
        # 키 역순, 인덱스 삽입
        for person in people:
            heapq.heappush(heap, (-person[0], person[1]))

        result = []
        # 키 역순, 인덱스 추출
        while heap:
            person = heapq.heappop(heap)
            result.insert(person[1], [-person[0], person[1]])
        return result

 

• 첫 번째 값이 큰 순서대로 추출되는 최대 힙, 두 번째 값은 삽입되는 인덱스로 활용