LeetCode #406 Queue Reconstruction by Height

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #406. Queue Reconstruction by Height

문제 풀이

그리디 알고리즘으로 해결할 수 있는 문제다. 우선 다른 원소들과 비교했을 때 키가 클수록 다른 원소에 영향을 받지 않으므로 키에 대해 내림차순으로 정렬하고 동일 키에 대해 앞 사람들 중 자신의 키 이상의 사람의 수가 적을 수록 앞쪽에 위치하며 뒤의 사람에 대해 영향을 받지 않으므로 앞자리 사람이 적은 오름차순으로 정렬한다.

리턴할 새 배열을 생성하고 정렬된 원소들에 대해 차례대로 자신의 키 이상인 앞사람의 수를 인덱스 삼아 삽입한다.

자신의 키 이상인 앞사람의 수를 기준으로 삽입하는 이유는 우선 자신보다 크거나 같은 사람이 이미 줄을 선 시점에서 자신의 키 이상인 앞사람의 수는 그 시점에서의 좌표를 의미하기 때문이다.

python 코드

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