파이썬 백준 1933 스카이라인 (스택과 큐를 곁들인)

import sys   input = sys.stdin.readline import heapq l = [] n = int(input()) for i in range(n) :     elem = list(map(int, input().split()))     l.append(elem) l.append([0, 0, 1000000002]) l.append([1000000001, 0, 1000000002]) l.sort(key=lambda x : (x[0], -x[1])) heap = [[0, 0, 1000000002]] for a, h, b in l :     if a == 0 :         continue     else :         trash = []         hnow = 0         while heap[0][2] <= a :             t = heapq.heappop(heap)             heapq.heappush(trash, [t[2], -t[0]])         if trash != [] :             stack = []             for i in range(len(trash)) :                 high = heapq.heappop(trash)                 while stack != [] and stack[-1][1] <= high[1] :                     del stack[-1]                 stack.append(high)                             for i in range(len(stack) - 1) :                 print(stack[i][0], stack[i+1][1], end = ' ')             if stack[-1][0] == a :                 hnow = stack[-1][1]                 if hnow > h :                     print(stack[-1][0], h, end = ' ')             else :                 print(stack[-1][0], -heap[0][0], end = ' ')                         if h > -heap[0][0] and h > hnow :             print(a, h, end = ' ')         heapq.heappush(heap, [-h, a, b])

시험시간은 30분인데 300분을 매달린 문제ㅋㅋ

 

처음 아이디어는 힙과 스택의 조합이었다.

건물을 리스트에 담아 시작점 순으로 정렬하고 for문을 돌려서, 각 건물의 차례가 올때마다 그 건물을 높이최대순 정렬 힙에 넣는다.

이때 힙에 넣기 전에 루트에 있는 원소(=높이가 최대인 건물)의 끝점이 지금 건물의 시작점보다 작다면, 이미 지나간 건물이니 힙에서 내보낸다. (※)

이를 while문으로 반복하고 나면 루트에 있는 원소는 아직 지나가지 않았으면서도 높이가 최대인 건물이다.

(이미 지나간 모든 건물을 지우진 않았지만, 높이가 최대가 아니라면 코드에서 하는 일이 없기 때문에 힙에 있든 말든 상관이 없다. 만약 자기가 루트가 되는 차례가 온다면 그때 나갈 것이다.)

이 높이최댓값과 지금 힙에 넣을 건물의 높이를 비교하여, 더 높다면 print한다.

 

힙을 이용한 여기까지의 구현으로 새로 들어오는 건물에 의한 스카이라인 상승은 모두 출력할 수 있다.

그렇다면 힙에서 나가는 건물에 의한 스카이라인 하락을 구현해야 하는데, 이때의 아이디어가 스택이다.

 

(※)에서 while문에 의해 삭제되는 heap의 원소들을 stack에 담는다. 이때, 기존에 stack에 있던 원소 중 자기보다 높이가 낮은 원소는 삭제한다. 2493 탑의 코드(https://uneducatedjungler.tistory.com/32)와 원리가 같다.

(탑 문제는 결국 각각의 탑이 시작점이 마이너스 무한대인 건물일때 스카이라인을 구하는 문제인 셈이다.)

그래서 이 부분은 이미 잘 돌아가는걸 확인한 탑의 코드를 참고하여 구현했다.

 

여기까지 왔을땐 이제 다 푼줄 알아서 좋았지...

 

그런데 서로 다른 기능을 하는 이 두 코드를 합치자 대환장파티가 펼쳐졌다.

testcase처럼 서로 각자 기능을 할땐 출력을 잘 하는데, 같은 곳에서 여러 건물이 시작될 때, 여러 건물이 끝날 때, 어떤 건물이 끝나는데 다른 건물은 시작될 때 등 몇몇 예외에서 쓸모없는 출력을 해서 출력초과가 떴다.

몇개 고치고 나니 더이상 틀린 부분을 찾기도 힘든데, 어디서 어떤 예외가 남은건지 백준은 알려주지도 않아서 몇시간동안 코드를 쳐다보며 오만가지 경우를 생각해본 것 같다.

 

스카이라인이 하락하는 경우를 체크하는 코드에서는 for문에서 이번에 들어오는 (아직 힙에 안들어간) 건물의 h를 참고하고, 이번 건물의 시작점에 끝나는 건물이 있다면 스카이라인이 상승하는 경우를 체크하는 코드를 위해 높이를 기록해서(hnow) 넘겨주는 식으로 서로가 서로를 보완하게 하자 정답처리가 되었다.

 

이걸 30분동안 풀라고 주신 코치님... 우리가 그분의 눈높이에 닿는 날이 올까요...?