Queue Reconstruction by Height (Priority Queue)

하루히즘·2021년 7월 19일
0

LeetCode

목록 보기
17/17
post-thumbnail

설명

LeetCode의 Queue Reconstruction by Height 문제다.

사람들을 일렬로 세웠을 때 앞에 자신보다 키가 크거나 같은 사람이 몇 명이나 있는지와 각자의 키가 주어질 때 이들을 알맞게 배치시키는 문제다.

예를 들어 [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]처럼 주어진다면 이는 첫 번째 사람은 키가 7이며 자신 앞에 아무도 없다. 즉 자신보다 키가 크거나 같은 사람이 없다. 두 번째 사람은 키가 4며 자신보다 키가 크거나 같은 사람이 4명, 세 번째 사람은 키가 7이며 자신보다 키가 크거나 같은 사람이 1명이 있다는 것을 나타낸다.

이 경우 키와 조건에 맞게 재배열하면 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]처럼 된다. 첫 번째 사람은 키가 5며 앞에 자신보다 키가 크거나 같은 사람이 없다. 중요한 것은 순서는 키 순서가 아니라 자기 앞에 몇 명이 있는지를 기준으로 세워야 한다는 것이다. 그래서 두 번째 사람은 키가 7이며 역시 앞에 자신보다 키가 크거나 같은 사람은 없으며 이후도 동일하다.

풀이

우선순위 큐 #1 (380ms)

문제에서 활용할 수 있는 가장 큰 단서는 자신 앞에 몇 명이나 있는지다. 하지만 위의 [5, 0]과 [7, 0]처럼 동일한 값을 가지는 사람이 있기 때문에 헷갈릴 수 있는데 여기서 생각해 볼 점은 문제에서 제공하는 것이 자신보다 크거나 같은 키의 사람들이란 것이다.

그렇기 때문에 일단 사람들을 정렬하고 가장 큰 사람들부터 자기 앞에 사람이 적은 순서대로 배치해야 한다. 그리고 그 다음으로 큰 사람들을 동일하게 배치하면 되는데 이 때 자신의 위치에 삽입하면서 기존에 삽입했던, 현재 사람보다 더 큰 사람들이 밀려나면서 순서가 맞춰지게 된다.

큰 사람들은 자신보다 작은 사람들이 자신의 앞이나 뒤에 어떻게 배열되는지, 자기가 어디까지 밀려나는지 신경쓸 필요가 없다. 왜냐면 자신보다 크거나 같은 사람들의 수만 맞춰주면 되기 때문에 자신보다 작은 사람들은 그 사이로 자유롭게 배치될 수 있는 것이다.

또 하나 중요한 점은 동일한 키의 사람이 있다면 자기 앞에 있는 사람들의 수가 적은 사람부터 삽입되어야 한다. 그래야 많은 쪽에서 자기와 동일한 키의 사람도 포함해서 셀 수 있기 대문이다.

이를 그림으로 보이면 다음과 같다.

세 번째, 네 번째를 보면 [5, 0]과 [5, 2]가 있을 때 [5, 0]이 먼저 삽입된 것을 볼 수 있다. 그리고 [5, 2]가 삽입될 때 먼저 삽입된 맨 앞에 있는 [5, 0]도 반영하여 인덱스 2에 삽입될 수 있다.

이를 기반으로 구현한 코드는 다음과 같다.

import heapq


class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        heap = []
        # 우선순위 큐에 키가 큰 순서, 앞에 사람이 적은 순서대로 삽입.
        for person in people:
            height, others = person
            heapq.heappush(heap, (-height, others))
            
        answer = []
        while heap:
            # 힙에서 키가 큰 사람을 추출.
            height, others = heapq.heappop(heap)
            height = -height
            
            count = 0 # 자신 앞에 몇 명이나 있는지 확인.
            index = 0 # 줄에 삽입할 위치.
            
            # 줄 서있는 사람들과 비교하여
            for existingPerson in answer:
                # 만약 자신 앞에 있는 사람들의 수와 같다면 탐색 중단.
                if count >= others:
                    break
                    
                # 현재 사람이 자신보다 키가 크거나 같다면 count 증가.
                if existingPerson[0] >= height: 
                    count += 1
                
                # 줄에 삽입할 위치의 포인터 증가.
                index += 1
                
            # 현재 위치에 줄 세우기.    
            answer.insert(index, (height, others))
            
        return answer

리스트의 insert 메서드가 문제에서 요구하는 풀이와 부합하기 때문에 이를 활용하는 것이 중요한 역할이다.

우선순위 큐 #2 (100ms)

더 좋은 해결방법은 없을지 찾아보다가 다른 풀이에서 아래와 같은 방법을 볼 수 있었다. 불필요한 비교 및 탐색 과정을 제거하고 바로 리스트에 삽입하는 방식이었는데 우선순위 큐의 정렬 방식이 앞에 사람이 적은 순서대로인 것과 리스트의 삽입 메서드가 기존 요소를 한 칸씩 밀어내고 자기가 그 위치에 삽입된다는 것을 활용한 좋은 풀이였다.

import heapq


class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        heap = []
        # 마찬가지로 키가 큰 순서대로, 앞에 사람이 적은 순서대로 힙에 삽입.
        for person in people:
            height, others = person
            heapq.heappush(heap, (-height, others))
            
        answer = []
        while heap:
            # 이번에는 힙에서 꺼내서 그대로 리스트에 삽입.
            height, others = heapq.heappop(heap)
            # 삽입 메서드는 범위를 벗어나면 맨 뒤에 삽입하는 걸로 처리.
            # 기존 요소를 한 칸 뒤로 밀어내고 자신을 삽입하는 특징.
            answer.insert(others, (-height, others))
            
        return answer

후기

쉽게 생각하고 접근했다가 막상 풀려니 까다로웠던 문제지만 키가 큰 사람 먼저, 자기 앞에 사람들이 적은 사람 먼저 그리고 자기보다 키가 작은 사람들이 자기 앞이나 뒤에 얼마나 들어오든 영향을 끼치지 않는다는 점에 집중하면 해결할 수 있었던 것 같다.

profile
YUKI.N > READY?

2개의 댓글

comment-user-thumbnail
2021년 7월 20일

글씨가 정말 예쁘시네요

1개의 답글