Algorithms/LeetCode
LeetCode #406 Queue Reconstruction by Height
8iggy
2021. 7. 19. 22:15
읽기 전
- 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
- 개인적으로 배운 점을 정리한 글입니다.
문제 링크
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