[백준 1933번] 스카이라인 (Python3)

import sys
input = sys.stdin.readline
from heapq import *

N = int(input())

stack = []
hq = []
for i in range(N):
  heappush(hq,tuple(map(int,input().split())))

end = 0
while hq:
  l,h,r = heappop(hq)
  if l >= end:
    if l > end:
      stack.append((end,0))
      stack.append((l,h))
    else:
      if h != stack[-1][1]:
        stack.append((l,h))
    end = r
    continue
  if h <= stack[-1][1]:
    if r > end:
      heappush(hq,(end,h,r))
    continue
  if end > r:
    heappush(hq,(r,stack[-1][1],end))
  if l == stack[-1][0]:
    stack.pop()
  stack.append((l,h))
  end = r
stack.append((end,0))
for i in range(1,len(stack)):
  print(*stack[i],end=" ")

우선순위 큐를 활용하여 해결하였다.

 

히스토그램 [백준 1725번] 히스토그램 (Python3) (tistory.com) 문제와 비슷한 방식으로 해결하였다. 히스토그램 문제를 처음에는 우선순위 큐를 이용해서 풀었었는데 그때의 경험이 도움이 되었다.

 

알고리즘을 설명하면,

1. 모든 입력을 (left,height,right)의 튜플로 최소힙큐에 넣어준다.

2. stack에는 (left,height)를 쌓고, right 값은 end로 저장한다.

3. 만약 힙큐에서 pop한 값의 left값이 end보다 크다면, 그 사이에 건물이 없다는 뜻이므로 stack에 (end,0)을 추가한다.

4. left값이 end와 같으면, 높이가 같은 경우에는 end만 바꿔주고, 나머지의 경우에는 stack에 (left,height)를 추가한다.

5. left값이 end보다 작은 경우 (즉 건물이 겹치는 경우) 현재 높이와 이전의 높이를 비교한다

6. 현재 높이가 더 작은 경우 stack은 갱신하지 않고 right가 end보다 큰 경우, 힙큐에 (end,height,right)로 다시 넣는다.

7. 현재 높이가 더 큰 경우, stack을 갱신하고 end가 right보다 큰 경우, 힙큐에 (right,이전높이,end)로 다시 넣는다.

8. 스택을 차례대로 출력한다.

 

조건분기가 여러개라서 설명이 좀 길지만 막상 짜보면 굉장히 간단하게 구현할 수 있다.

 

 

오늘의 교훈) 다양한 풀이를 도전하자