[Python 3] BOJ - 1933 "스카이라인"

 # 문제 링크

https://www.acmicpc.net/problem/1933

1933번: 스카이라인

 

 # 풀이

 개인적으로 이 문제의 핵심은 우선순위 큐와 정렬과 set의 적절한 사용이라고 생각한다. 고려해야 할 것이 많은 어려운 문제이다.

<그림 1. 예제 1의 경우>

  위 사진은 문제 링크에 있는 사진을 발췌한 것에 약간의 수정을 한 것이다. 빨간 점은 갑자기 높이가 상승했기 때문에 스카이라인의 경계가 되는 부분이며, 파란 점은 갑자기 높이가 하강했기 때문에 스카이라인의 경계가 되는 부분이다. 그런데 두번째 파란점을 보면 빨간점에서의 높이가 끝날 때 아직 끝점에 도달하지 않은 건물들의 높이 중 가장 큰 것을 알 수 있다. 세번째 파란점 역시 네번째 빨간점이 끝난 시점 기준으로 끝점에 도달하지 않은 건문들의 높이 중 가장 큼을 알 수 있다. 따라서, 전체 구간에서 끝나지 않은 건물 중 가장 높은 높이를 저장해야만 한다. 그런데 예외적으로 첫번째 파란점은 끝나지 않은 건물이 없기 때문에 높이가 0이 되는 모습을 알 수 있다. 따라서 우선순위 큐(최대 힙)를 써야 그 다음 높은 높이를 구하는데 효율적이다.

<그림 2. 시작점과 끝점의 우선순위>

 위에서 우리는 우선순위 큐를 써야 함을 알아냈다. 그런데 전제는 제일 처음 시작점부터 끝점까지 순회하는 경우이다. 따라서 각 건물의 시작점과 끝점으로 나누어 오름차순으로 정렬해야 함을 알 수 있다. 그런데 그림 2는 한 지점에서 파란점과 빨간점이 동시에 나타나는 경우이다. 만일 파란점, 즉 건물이 끝나는 것을 건물이 시작하는 것보다 우선하게 된다면 이 때 스카이라인의 높이가 0이 된다. 그런데 실제로는 스카이라인의 높이가 0이 아니라 빨간점이 된다. 따라서 건물이 시작하는 것이 건물이 끝나는 것보다 더 우선시되어야 한다. 따라서, 시작점과 끝점을 분리한 후, 같은 지점이라면 시작점을 우선하도록 정렬해야 한다

<그림 3. 같은 시작점에 대한 우선순위>

 위 그림 3은 같은 시작점이지만 다른 높이를 가지는 건물의 경우이다. 만일 더 작은 건물의 높이가 더 큰 건물의 높이보다 우선순위를 가진다면, 스카이라인이 같은 시점에서 두 개가 생겨버린다. 이는 명백한 오류이다. 따라서, 이러한 예외를 해결하기 위해서는 같은 시작시점을 가지는 경우는 더 높은 건물이 우선순위를 가짐으로서 해결할 수 있다.

<그림 4. 같은 끝점에 대한 우선순위>

 그림 4는 그림 3과 달리 같은 끝점을 가지지만 각자 높이가 다른 경우이다. 이런 경우는 자칫하면 파란점의 갯수만큼 스카이라인을 가질 수 있다. 역시 스카이라인은 한 시점에서 단 하나만 가져야 하므로 현재 그림 4의 경우는 스카이라인의 높이가 0이 되어야 한다. 이것을 해결하는 방법은 여러가지 방법이 있지만 다른 건물에서 현재 끝점에서 끝난 건물이 있는지 아닌지를 확인해야 하기 때문에 set을 이용하였다. 왜냐하면 set은 중복이 없고 원소 조회에 O(1)이 걸리기 때문이다. 

 그런데 위에서 파란점일 때는 우선순위 큐에서 그 다음으로 높은 높이를 구해야 한다고 했다. 그러므로 다음 높은 높이가 이미 끝난 시점의 높이인지 판단해주면서 이미 끝나지 않았다면, 즉 set에 없다면 그 높이가 바로 그 다음 높은 높이가 된다. 반대로 set에 있다면 이전에 끝난 높이이므로 pop을 해주면 그림 4와 같은 경우를 처리할 수 있다. 따라서, 우선순위에 각 건물의 높이뿐만 아니라 그 건물이 끝나는 시점도 같이 저장해줘야 한다

 

  # 코드

import sys, heapq

# 입력부
n = int(sys.stdin.readline())
arr = []
height = [0] * n
q = []

# end : 현재 index번째 건물의 끝나는 지점을 저장하는 리스트
end = [0] * n
# check : 현재까지 끝난 끝점을 저장하는 set
check = set()
for i in range(n):
    a, b, c = map(int, sys.stdin.readline().split())
    # 시작점이면 1, 끝점이면 -1
    arr.append((a, i, 1))
    arr.append((c, i, -1))
    height[i] = b
    end[i] = c

# 그림 2, 그림3에 따라 정렬
# 첫번째 우선순위 : 시점이 앞서는지
# 두번째 우선순위 : 시점이 같다면 시작점인지
# 세번째 우선순위 : 시점도 같고 둘 다 시작점이면 높이가 더 높은지
arr.sort(key=lambda x : (x[0], -x[2], -height[x[1]]))

# now : 현재 최고높이
now = 0
ans = []
for i in range(len(arr)):
    # point : 시점, idx : 건물의 인덱스, dir : 시작점인지 끝점인지
    point, idx, dir = arr[i]
    
    # 시작점인 경우(빨간점)
    if dir == 1:
        # 높이가 갱신된다면 그 부분이 새로운 스카이라인
        if now < height[idx]:
            now = height[idx]
            ans.append((point, now))
        # 높이가 갱신됨과 상관없이 현재 건물의 높이와 끝점을 최대 힙에 저장
        heapq.heappush(q, (-height[idx], end[idx]))
        
    # 끝점인 경우(파란점)
    else:
        # 현재 시점이 끝났기 때문에 set에 끝점의 시점을 저장
        check.add(point)
        # 최대 높이가 끝난 건물이 아닐때까지 pop
        while q:
            if q[0][1] not in check:
                break
            heapq.heappop(q)
            
        # 힙이 비었다면 스카이라인의 높이는 0으로 갱신
        if not q:
            if now:
                now = 0
                ans.append((point, now))
                
        # 힙이 있다면 현재 높이와 비교 시 변동이 있다면 그 높이가 그 다음으로 높은 건물이기 때문에
        # 스카이라인 높이 갱신
        else:
            if -q[0][0] != now:
                now = -q[0][0]
                ans.append((point, now))

# 정답 출력
for i in ans:
    print(i[0], i[1], end=' ')