leetcode : The Skyline Problem

https://leetcode.com/problems/the-skyline-problem/

The Skyline Problem - LeetCode

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

왤케 어려워 진짜...

이 문제는 정답 보고 이해해가면서 간신히 구현했다.

혼자 할래다가 나중엔 그냥 거의 정답 따라하다시피 했다ㅠㅠ 나 왜이렇게 머리가 안좋은지 자괴감이 뿜뿜..

(정답을 봐도 구현하기 힘든 문제들은 알고보면 죄다 구글 기출)

 

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        events = []
        events += [[l,-h,r] for l,r,h in buildings]
        events += [[r, 0, 0] for l,r,h in buildings]
        events.sort()
        
        answer = [[0,0]]
        maxheap = [[0, float("inf")]] # -height,  right
        
        for start, nh, end in events:
            while start >= maxheap[0][1]:
                heapq.heappop(maxheap)
                
            if nh:
                heapq.heappush(maxheap, [nh, end])
                
            if answer[-1][1] != -maxheap[0][0]:
                answer.append([start,-maxheap[0][0]])
            
        return answer[1:]

정답코드 자체는 참 짧고 간단해보인다.

 

일단 기본 intuition을 생각해보자.

직관적으로 관찰해보면 세 가지 타입의 포인트가 있다.

A : 건물의 시작점이며 이전의 건물보다 높게 솟은 포인트

B :  건물의 끝부분이며 이전에 시작된 가로로 긴 건물이랑 교차하는 지점

C :  건물 영역의 끝부분

 

내가 어떤 포인트를 검사하고 있을 때 이 포인트가 특정 건물의 영역에 있는지 ( left < 포인트 x좌표 < right )를 항상 신경써야 한다.

특히 B부분의 좌표를 계산할 때에는 이전에 시작됐던 건물중에 아직 끝나지 않았으면서 높이가 제일 큰 건물을 찾아야한다. (그래서 max heap이 필요하다. 건물들을 높이순으로 촵촵 넣어줘야됨!)

 

B와 C를 묶어서 생각해보면 둘은 건물의 끝부분이다. 그니까 우리가 input 리스트를 검사하면서 건물의 시작점인 A나 끝점인 B,C를 정답리스트에 추가해가려면 "나 건물의 끝부분이에요!"하는 데이터도 필요하다. 여기서 events 변수를 만들었다. 기존의 input리스트는 건물의 시작 이벤트라고 생각하고 건물 끝좌표들을 따로 만들어 건물 끝 이벤트로 넣어서 정렬해줄거다.

events = []
events += [[l,-h,r] for l,r,h in buildings]
events += [[r, 0, 0] for l,r,h in buildings]
events.sort()

벌써 머리가 복잡해질것이다.

l,-h,r 순서로 시작이벤트를 넣은 이유는 정렬 순서를 내가 원하는 대로 맞추기 위해 변형한거기 때문이다.

l : 건물의 시작점을 가장 높은 우선순위로 정렬한다.

-h : 시작점이 같다면 높은 건물이 먼저 나오도록한다. (리스트 메서드 sort가 기본적으로 오름차순 정렬이기 때문에 내림차순 정렬하려면 -를 붙여 부호를 반전시켜야 한다.)

r : 시작점도 같고 높이도 같다면 짧은 건물이 먼저 나온다.

 

끝 이벤트는 높이를 0으로 함으로써 표현했다. 이제 events 리스트를 순회해가면서 저 부분이 0이면 끝 이벤트임을 알 수 있고 0이 아니면 시작 이벤트임을 알 수 있다.

 

answer = [[0,0]]
maxheap = [[0, float("inf")]] # -height,  right

정답변수와 maxheap을 초기화 한다. 뭔가 초기값을 넣고있는데 추후 구현을 단순하게 하기 위한 더미 데이터다. 왜 저런 더미 데이터를 넣는지는 뒤쪽 코드를 봐야 이해가 된다 ㅠㅠ 저 더미데이터 때문에 마지막에 정답 리턴할 때

return answer[1:]

이렇게 더미데이터는 빼고 리턴함.

 

for start, nh, end in events:
    while start >= maxheap[0][1]:
        heapq.heappop(maxheap)

    if nh:
        heapq.heappush(maxheap, [nh, end])

    if answer[-1][1] != -maxheap[0][0]:
        answer.append([start,-maxheap[0][0]])

핵심 로직을 보도록 하자.

start : 건물의 시작지점 ( 끝 이벤트일 경우 끝 지점 )

nh : negative height, 건물의 높이에 -1이 곱해진거. (끝 이벤트일 경우 0)

end : 건물의 끝지점 ( 끝 이벤트일 경우 0 )

 

maxheap에는 데이터가 [-height, end] 형태로 들어간다.

파이썬 heap이 min heap이라서 max heap 구현을 위해 -1을 곱해서 넣는거다. end를 넣는 이유는 이 건물이 유효한지 확인하기 위해 넣는거다. 첫 while문을 보자.

while start >= maxheap[0][1]:
	heapq.heappop(maxheap)

 maxheap[0]은 힙의 루트노드다. [-height,end]형태로 들어간다고 했으니 maxheap[0][1]은 -height가 가장 작은 데이터의 end값이다. 즉! "지금까지 나왔던 건물들 중에 높이가 가장 큰 건물이 끝나는 지점"을 의미한다. 이거보다 현재 보고 있는 이벤트의 시작지점(start)이 같거나 크면 이 데이터는 더이상 유효하지 않으니 빼버리는거다.

 

 

이제 maxheap의 루트노드엔 지금까지 봤던 건물중에 가장 높고 아직 유효한(끝나지 않은) 건물이 있을거다.

 

if nh:
    heapq.heappush(maxheap, [nh, end])

if answer[-1][1] != -maxheap[0][0]:
    answer.append([start,-maxheap[0][0]])

이건 묶어서 보자

if nh: 그니까 이게 시작 이벤트면

힙에 현재 건물의 높이와 끝부분을 푸시한다.

여기서 경우의 수가 두 갈래로 나뉘어 버리는거다.

1. 시작이벤트면 : 힙의 루트노드엔 현재 건물의 높이와 끝지점이 들어있다.

2. 끝이벤트면 : 힙의 루트노드엔 유효한 건물중 가장 높은 건물의 높이와 끝지점이 들어있다.

 

answer[-1][1]  != -maxheap[0][0]을 해석해보자.

 

answer[-1] : 가장 마지막에 추가한 정답

answer[-1][1] : 의 높이가

!= : 같지 않으면

-maxheap[0][0] : 힙 루트노드에 있는 건물의 높이와

 

시작 이벤트일경우 : "현재 건물 높이랑 최근에 정답에 추가한 포인트 높이랑 다르면"

끝 이벤트일경우 : "유효한 건물중 가장 큰 건물 높이랑 최근에 정답에 추가한 포인트 높이랑 다르면"

묶어서 생각해보면 정답 포인트를 추가할때 높이가 될 값이랑 최근에 추가한 값이랑 비교하는거다.

그림을 다시보면

 

A,B,C 모두 x좌표는 이벤트의 시작점 좌표고

y좌표는 "현재 유효한 건물중 가장 큰 건물 높이"다.

이렇게 단순하게 정리되다니.

 

다시 전체 코드를보자

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        events = []
        events += [[l,-h,r] for l,r,h in buildings]
        events += [[r, 0, 0] for l,r,h in buildings]
        events.sort()
        
        answer = [[0,0]]
        maxheap = [[0, float("inf")]] # -height,  right
        
        for start, nh, end in events:
            while start >= maxheap[0][1]:
                heapq.heappop(maxheap)
                
            if nh:
                heapq.heappush(maxheap, [nh, end])
                
            if answer[-1][1] != -maxheap[0][0]:
                answer.append([start,-maxheap[0][0]])
            
        return answer[1:]

 

이런 엣지케이스는 어떻게 해결되는걸까?

events = []
events += [[l,-h,r] for l,r,h in buildings]
events += [[r, 0, 0] for l,r,h in buildings]
events.sort()

정렬할 때 시작이벤트가 먼저 오게 돼있다.

 

if answer[-1][1] != -maxheap[0][0]:

중간에 겹치는 부분의 시작 이벤트는 이 코드에서 걸려져서 정답리스트에 추가되지 않는다.

끝 이벤트는 시작 이벤트 뒤에 오게 되는데 -maxheap[0][0]은 방금전에 추가한 시작이벤트 지점의 높이고 이전에 정답에 추가한 데이터(첫번째건물)과 높이가 같기때문에 여기서 걸러진다.

 

이걸 어떻게 45분만에 라이브면접에서 풀어? 구글에 대체 어떤 사람들이 들어가는거야?