백준 1933 스카이라인

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

반년만의 백준 풀기

문제에서 일단 구해야 할 것은 (명시되어있진 않지만) $x=0$, 높이$=0$ 부터 시작해서 $x=inf$ 까지 높이 변화 위치와 해당 높이입니다.

이를 위해선 각 위치에서 겹쳐져 있는 각 건물들의 높이를 관리하면 됩니다. 건물의 왼쪽 끝 $x$좌표와 오른쪽 끝 $x$좌표를 정렬해서 풀 수 있습니다. 정렬하면 $x=0$ 부터 시작해 $x$를 늘려나감에 따라 만난 새로운 건물과, $x$좌표 범위에서 벗어난 건물을 빠르게 처리할 수 있습니다.

다만 $x$좌표의 범위가 굉장히 넓으므로, 모든 $x$에 대해서 반복하면 안됩니다. 이는 회의실 배정 문제랑 동일한 문제입니다.

어떤 위치 $x$에 대해 어떤 건물이 포함되어 있는지는 알더라도, 그중에서 가장 높이가 큰 건물을 빠르게 구할 방법이 필요합니다. 이와 동시에 새로 포함된 건물, 제외된 건물의 높이를 처리할 수 있어야합니다.

1. set
2. 우선순위 큐

우선순위 큐를 쓴다면, 제거되는 건물이 항상 가장 높은 건물이 아니므로 단순히 현재 위치에 포함된 건물들의 높이를 관리하는 우선순위 큐 하나로는 충분하지 못합니다.
예를 들어, 우선순위 큐가 현재 ${10, 4, 2, 1}$ 이 상태이고, 제외할 건물의 높이가 $2$라면, $2$를 우선순위 큐로는 바로 제거할 방법이 없습니다.

따라서 삭제된 높이들을 관리하는 우선순위큐를 하나 더 가지고 있으면 됩니다.
높이를 관리하는 우선순위 큐를 $H$, 삭제된 높이들을 관리하는 우선순위 큐를 $D$ 라고 하면, $H[0]$ 과 $D[0]$ 이 동일할 때 $H, D$ 양쪽 모두에서 pop해주면 됩니다. 가장 높은 높이의 건물이 아니라면 당장 $H$에서 제거되지 않아도 상관이 없기 떄문입니다.

set을 쓰는 방법은 방금 내용을 읽었다면 쉽게 떠올릴 수 있습니다.

시간 복잡도는 정렬에 건물 $N$개에 대해서 $O(NlogN)$, 우선순위 큐(혹은 set의 경우)는 $N$번 삽입/삭제가 일어나므로 일반적인 구현에선 $O(NlogN)$ 입니다. 전체적으로 $O(NlogN)$에 계산될 수 있습니다.