스카이라인
플래티넘 IV의견: 0
도시의 실루엣(스카이라인)을 그리려고 한다. 평지 위에 \(N\)개의 직사각형 건물이 서 있고, \(i\)번째 건물은 \((L_i, R_i, H_i)\)로 주어진다. 이는 가로 구간 \([L_i, R_i]\) 위에 높이 \(H_i\)의 건물이 서 있다는 뜻이다 (건물들은 서로 겹치거나 포개질 수 있다).
모든 건물을 합쳐서 만들어지는 윤곽선(스카이라인)을 키 포인트들의 수열로 출력하여라. 키 포인트란 윤곽선의 높이가 변하는 지점으로, \([x, h]\)는 가로 좌표 \(x\)에서 윤곽선의 높이가 \(h\)로 바뀐다는 뜻이다. 키 포인트는 \(x\)좌표 오름차순으로 나열되며, 윤곽선이 땅으로 내려오는 마지막 점은 높이 \(0\)인 키 포인트로 표현된다.
연속한 두 키 포인트의 높이는 절대 같지 않다 (불필요한 점은 출력하지 않는다).
\(1 \le N \le 100\,000\), \(1 \le L_i < R_i \le 10^9\), \(1 \le H_i \le 10^9\).
첫째 줄에 건물의 개수 \(N\)이 주어진다.
이어지는 \(N\)개의 줄에 각각 세 정수 \(L_i\), \(R_i\), \(H_i\)가 공백으로 구분되어 주어진다.
첫째 줄에 키 포인트의 개수 \(K\)를 출력한다.
이어지는 \(K\)개의 줄에 각각 키 포인트의 좌표 \(x\)와 높이 \(h\)를 공백으로 구분하여 \(x\) 오름차순으로 출력한다.
5
2 9 10
3 7 15
5 12 12
15 20 10
19 24 8
7
2 10
3 15
7 12
12 0
15 10
20 8
24 0
LeetCode-218의 고전 예시. 윤곽선은 \((2,10),(3,15),(7,12),(12,0),(15,10),(20,8),(24,0)\)로 바뀐다.
1
1 5 3
2
1 3
5 0
건물이 하나뿐이므로 \(x=1\)에서 높이 \(3\)으로 올라가고 \(x=5\)에서 \(0\)으로 내려온다.
riseoj 작성
출처 Original
평가 및 의견
스카이라인
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
스카이라인