파이썬 백준 1933 스카이라인 (스택을 손절한)

import sys   input = sys.stdin.readline import heapq l = [] xpick= {0} n = int(input()) for i in range(n) :     elem = list(map(int, input().split()))     l.append(elem)     xpick.add(elem[0])     xpick.add(elem[2]) l.sort(key=lambda x : (x[0], -x[1])) xpick = sorted(list(xpick)) del xpick[0] i = 0 heap = [] for now in xpick :     while i < n and l[i][0] == now :         if heap == [] :             print(l[i][0], end = ' ')             print(l[i][1], end = ' ')         elif l[i][1] > -heap[0][0] :             print(l[i][0], end = ' ')             print(l[i][1], end = ' ')         heapq.heappush(heap, [-l[i][1], l[i][2]])         i = i + 1     if heap != [] and now == heap[0][1] :         high = heapq.heappop(heap)         while heap != [] and now >= heap[0][1] :             heapq.heappop(heap)         if heap == [] :             print(high[1], end = ' ')             print(0, end = ' ')         elif high[0] != heap[0][0] :             print(high[1], end = ' ')             print(-heap[0][0], end = ' ')

https://uneducatedjungler.tistory.com/62

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

스택 파트의 코드와 큐 파트의 코드를 합치는 환장의 콜라보를 몇시간동안 고치던 중, 정답자 형님의 은총을 받아 스택을 쓰지 않아도 풀 수 있는 방법을 알게 되었다.

이렇게 생고생을 할거면 차라리 하나를 안쓰는게 낫지 않나 싶어서 그쪽으로 방향을 틀었다.

사실 이쪽을 먼저 정답처리 받았고, 저건 그냥 오기가 생겨서 마지막까지 붙잡고 고친 셈이다ㅋㅋ

스택을 쓴다면 각 건물의 시작점마다 for문을 돌려서 이전에 미리 끝나있던 건물에 의한 변화까지 고려하려니 상황이 복잡해지는 것인데, 차라리 시작점과 끝점을 모두 x라는 하나의 리스트에 담아 for문을 2배의 길이로 돌린다면 상황이 편해지지 않을까 하는 아이디어의 접근이다.

새 건물이 시작되는 x라면 스카이라인 상승 파트의 코드가 작동하고, 건물이 끝나는 x라면 하락 파트의 코드가 작동하는 것.

 

인풋받은 건물의 [0]과 [2]를 모두 x라는 set에 넣어 중복은 없앤 뒤, 이를 리스트한다.

그리고 이 리스트에 대해 for문을 돌린다.

x가 시작점인 건물들이 있다면 힙에 넣으면서 스카이라인이 높아지는지 확인하고

x가 종료점인 건물이 있다면 힙에 빼면서 스카이라인이 낮아지는지 확인한다.

 

참쉽죠?

처음부터 이렇게 접근했다면 제때 풀 수 있었을 텐데...

비효율적인 아이디어를 냈지만 이게 비효율적이라는걸 깨닫지 못한 경험의 부족이었다.

이제 자러가자...