마천루 스카이라인
골드 II의견: 0
미래 도시 '리세 타워'에는 \(N\)개의 마천루가 늘어서 있다. 건물 \(i\)는 수평 구간 \([L_i, R_i)\)에 걸쳐 높이 \(H_i\)로 세워져 있다.
스카이라인은 외부에서 바라볼 때 보이는 건물 윤곽선으로, 수평 위치 \(x\)마다 그 위치를 덮고 있는 건물 중 가장 높은 높이로 정의한다. 건물이 없는 곳은 높이 \(0\)이다.
스카이라인의 변환점 목록을 출력하여라. 변환점이란 스카이라인 높이가 이전과 달라지는 위치이다. 위치 \(x\)에서의 변환점은 \((x,\ \text{새 높이})\) 형태로 나타낸다. 변환점은 \(x\) 좌표 오름차순으로 출력한다.
- \(1 \le N \le 100\,000\)
- \(0 \le L_i < R_i \le 10^9\)
- \(1 \le H_i \le 10^9\)
- 정수 좌표이다.
첫째 줄에 건물의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 건물 정보 \(L_i\), \(R_i\), \(H_i\)가 공백으로 구분되어 주어진다.
스카이라인의 변환점을 \(x\) 좌표 오름차순으로 한 줄에 하나씩 출력한다. 각 줄에는 위치 \(x\)와 새 높이 \(h\)를 공백으로 구분해 출력한다. 건물이 없거나 모든 건물이 같은 높이이면 출력할 변환점이 없는 경우도 있다.
스카이라인이 \(0\)으로 떨어질 때도 변환점으로 출력한다.
3
1 5 3
2 7 5
6 9 4
1 3
2 5
7 4
9 0
\(x=1\)에서 높이 \(3\)으로 시작, \(x=2\)에서 더 높은 건물(\(h=5\))이 시작되어 높이 \(5\)로 바뀐다. \(x=7\)에서 \(h=5\) 건물이 끝나고 \(h=4\) 건물이 남아 \(4\)로 바뀐다. \(x=9\)에서 \(0\)으로 끝난다.
2
1 3 4
3 5 4
1 4
5 0
두 건물이 \(x=3\)에서 붙어 있어 스카이라인은 \(x=1\)에서 높이 \(4\), \(x=5\)에서 높이 \(0\)으로만 변한다.
riseoj 작성
출처 Original
평가 및 의견
마천루 스카이라인
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마천루 스카이라인