파이썬 백준 1933스카이라인_bisect

 

1. 빌딩의 (왼쪽,높이) (오른쪽,높이) 정보를 집합으로 받아 정리해준다. 왼쪽의 높이에 -값을 넣어 주어 나중에 주어진 값이 왼쪽인지 오른쪽 인지 구분이 쉽도록 해준다.
   왼쪽을 기준으로 집합을 오름차순 정렬한다.
   
   
2. top 의 초기값은 0을 넣어주고 before 에 항상 이전 탑의 최대값이 저장되도록 해준다.
3. 저장된 빌딩 집합을 for문으로 돌려주어 왼쪽값이 들어왔을때 top에 높이를 저장해준다. 저장된 탑의 높이는 insort로 넣어 자동으로 오름차순 정렬되어 top[-1]은 항상 최대값을 가진다.
   만약 top[-1] 이 before(이전top[-1])과 같지 않다면 높이의 변경이 생긴것이므로 ans리스트에 append 해준다.
   
   왼쪽으로 들어오고 이전 top보다 작은 높이가 들어왔다면 insort 하며 자동으로 최대높이보다 낮은 index로 저장되기 때문에 ans 에 append  되지 않는다.
   
   오른쪽으로 들어왔을때는 항상 자신의 높이를 top리스트에서 삭제해준다. 자신의 위치를 찾기위해 bisect_left함수를 사용하였다.
   
   가장 마지막으로 지워지는 top리스트는 가장 높은값이며 그다음엔 top의 초기값인 [0]이 남게되어 오른쪽 값과 0을 ans에 append시켜준다.

최종코드

import sys
from bisect import bisect_left, insort 
input = sys.stdin.readline

N = int(input())

#빌딩 정보 받아옵니다. L 좌표 H정보 Y좌표
buildings = [list(map(int,input().split()))for _ in range(N)]

stack = []
heights = set() #집합

for building in buildings:
    L, H, R = building
    heights.add((L,-H))
    heights.add((R,H))
heights = sorted(heights)

ans, top = [],[0]
before = top[-1]  #가장 높은 정보를 저장하기 위함



for P, H in heights:
    if H<0: #왼쪽 
        insort(top, -H) 
    else:
        top.pop(bisect_left(top,H)) 

    if top[-1] != before:  
        ans.append([P, top[-1]])

        before = top[-1] 

for i in range(len(ans)):
    for n in range(2):
        print(ans[i][n],end=' ')​

참조 : https://www.snoopybox.co.kr/1995