406. Queue Reconstruction by Height

문제 링크 : https://leetcode.com/problems/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]]:
        ans = []
        for h, i in sorted(people, key = lambda x: (-x[0],x[1])):
            ans.insert(i, [h,i])
        return ans

22.09.05

다시 복습

최종적으로 인덱스열에 의해 정렬해야하기 때문에(문제에서 앞에 k명이 있다~~하는 조건이 있기 때문에 ) insert를 이용하여 I를 기준으로 ans에 insert하고

그전에 키 순으로 내림차순으로 정렬한다.