(1) 시작점을 기준으로 오름차순 정렬하여 건물의 번호를 매긴다.
(2) 각 건물의 시작점과 끝점에서, 더 높은 건물이 있다면 패스하고 없으면 그 시작점과 끝점의 높이를 출력한다.
(3) (2)에 해당하지 않는 끝점에 대해서, 현재 건물보다 더 낮은 건물이 있다면 0이 아닌 그 낮은 건물(낮은 건물 중 최대 높이)을 출력한다.
해설
(1) 모든 건물의 시작점과 끝점, 그리고 높이를 Building 구조체 배열로 저장한다.
struct Building{
int from;
int to;
int height;
}
(2) 구조체 배열을 vector<pair<int,int>> 형태, 이하 Result 형태로 분할한다. 높이가 변하는 지점의 x좌표와 그 때의 height를 pair<int,int> 로 저장하여 배열로 만든다.
Result merge_sort(vector<Building>&a, int left, int right){
if(left >= right){
Result ret;
ret.emplace_back(a[left].from, a[left].height);
ret.emplace_back(a[left].to, 0);
}
int mid = (left + right) / 2;
auto l = merge_sort(a, left, mid);
auto r = merge_sort(a, mid + 1, right);
return merge(l, r);
}
분할하는 과정에서 left >= right일 때, 즉 left와 right 빌딩이 하나밖에 남지 않았을 때 그 건물의 시작점과 끝점의 높이를 Result 자료형에 저장한다.
(3) 나눈 스카이라인의 후보가 될 수 있는 점들을 병합한다. left와 right에 있는 점들을 각각 차례로 비교하면서 탐색한다.
left의 x좌표가 right의 x좌표보다 작은 경우, (left의 x좌표, max(h1, h2))를 ret 배열에 추가한다.
left의 x좌표가 right의 x좌표보다 큰 경우, (right의 x좌표, max(h1, h2)) 를 ret 배열에 추가한다.
→ left 스카이라인에 right 스카이라인이 가려지는 상황이다. 따라서 최종 스카이라인은 left 스카이라인의 높이를 따라가야하므로, 기존의 right의 height에서 left의 height로 높이를 수정하여 저장한다.
Result merge(Result & left, Result & right){
int i = 0, j = 0;
int h1 = 0, h2 = 0;
while(i < left.size() && j < right.size()){
auto & u = left[i], v = right[j];
if(u.first < v.first) { // left의 x좌표가 더 작은 경우
int x = u.first;
h1 = u.second;
int h = max(h1, h2);
append(ret, make_pair(x, h));
i++;
} else { // right의 x좌표가 더 작은 경우
int x = v.first;
h2 = v.second;
int h = max(h1, h2);
append(ret, make_pair(x, h));
j++;
}
}
// 남은 것 넣어주기
while(i < left.size()){
append(ret, left[i]);
i++;
}
while(j < right.size()){
append(ret, right[i]);
j++;
}
return ret;
}
(4) 이 때, 정렬된 배열에 최종 스카이라인을 넣는 것을 단순히 push_back하면 안 된다. 연속 점 중에서 높이가 같은 것을 제거하고, 최종 배열에서 연속되는 점 중에 높이가 같은 점을 제거한다.
다 만든 배열에서 연속이고 높이가 같은 점을 제거하는 것으로 하여도 되지만, 해설에서는 append함수를 만들어서 이를 고려하여 ret 배열에 값을 추가해주었다.