https://leetcode.com/problems/queue-reconstruction-by-height/
<문제>
여러 명의 사람들이 줄을 서 있다. 각각의 사람은 [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에 넣어서 정렬한 뒤, 큰 값부터 꺼내며 정렬해 나간다는 것이 신기했다.
내가 이 풀이를 떠올릴 수 있을까?
'다전공_컴퓨터공학 > 알고리즘 문제풀이' 카테고리의 다른 글
[프로그래머스] 이분탐색 > 입국심사 (이분탐색을 어떻게 적용할 것인가?) (0) | 2021.02.23 |
---|---|
[파이썬 알고리즘] 19장 비트조작 - 싱글 넘버 (XOR의 사용) (0) | 2021.02.22 |
[파이썬 알고리즘] 17장 - 색 정렬 (leetcode 75) - 3 pointer 문제 (0) | 2021.01.29 |
[파이썬 알고리즘] 17장 가장 큰 수 (leetcode 179) - merge sort 이용 (0) | 2021.01.29 |
[프로그래머스] 그래프 - 순위 (0) | 2021.01.22 |