https://www.acmicpc.net/problem/1933
문제
> N개의 직사각형 모양의 건물들이 주어졌을 때, 스카이라인을 구해내는 프로그램을 작성하시오.
> 스카이라인은 건물 전체의 윤곽을 의미한다.
> 즉, 각각의 건물을 직사각형으로 표현했을 때, 그러한 직사각형들의 합집합을 구하는 문제이다.
> 예를 들어 직사각형 모양의 건물들이 위와 같이 주어졌다고 하자.
> 각각의 건물은 왼쪽 x좌표와 오른쪽 x좌표, 그리고 높이로 나타난다.
> 모든 건물들은 편의상 같은 높이의 지면(땅) 위에 있다고 가정하자.
> 위의 예에서 스카이라인을 구하면 아래와 같다.
접근
입력으로 들어온 빌딩의 정보를 (시작점, 높이), (끝점, -높이)로 X가 작은 순서로 우선순위 큐에 넣는데 X가 같으면 높이가 더 높은 좌표가 먼저 들어간다. 높이에 -를 달아주는 이유는, 빌딩이 끝났어요 라고 마킹해주기 위해서이다.
이제 우선 순위 큐에서 top에 있는 애들을 하나씩 가져와서 높이가 양수인지 음수인지 먼저 따져준다. 양수라면 맵에 높이를 키값으로 하여 값을 누적(++)해주고, 음수라면 높이의 절대값을 키값으로 가지는 맵에 차감(--) 해주며 만약 해당 키값의 밸류가 0이 되면 맵에서 erase해준다. 이 과정을 동일한 x좌표를 가진 애들한텐 while문으로 반복해주고 최종 변화결과만 기록해줄것이다.
이제 위 과정이 끝나고 나오면 높이를 재설정 해줘야한다.
맵에 원소가 있나보고 없다면 빌딩이 없으니까 0을 반환하고, 있다면 그 중 가장 높은 높이를 가져와 높이로 한다.
이 새로 잡은 높이가 기존에 설정했던 높이와 같다면 변화가 없으므로 넘어가고, 다르다면 이를 어떤 좌표에서 어떻게 변했나 출력해준다.
문제해결
> 빌딩의 정보를 x좌표가 빠른것 부터 처리하기 위해 우선순위 큐를 pair로 좌표,높이로 선언해준다.
> 정렬 기준 cmp는 x 좌표가 같다면 높이가 더높은걸 먼저, 다르다면 x좌표가 작은걸 먼저가게 정렬해준다.
> N개 만큼 빌딩의 정보를 입력받고 시작점,높이 / 끝점,-높이를 큐에 넣는다.
> 초기 높이 Height를 0으로 잡고, 큐가 빌 때 까지 while문에서 스카이라인을 탐색한다.
> 큐의 top()의 x좌표를 fL로 잡아오고, 이와 같은 x좌표에 대해 반복 처리해 최종 변화를 따지기 위해 또 while문을 들어간다.
> 쌍으로 들어온 높이를 fH로 잡고, pop해준다.
> fH가 양수 즉, 빌딩의 시작이면 fH를 key값으로 map인 sky에 저장해준다.
> 만약 음수라면 빌딩이 끝났으므로 음수로 마킹한 fH를 다시 양수로 바꿔주고 맵에서 감소시킨다.
> 만약 감소 시켰는데 0이 됐으면 해당 높이를 가지는 빌딩이 더 이상 없다는 뜻이므로 맵에서 erase해서 지워준다. 그래야 높이 판단이 제대로 된다.
> 이제 똑같은 x좌표가 있다면 다시 fH를 잡는것부터 시작할 것이고 없다면 높이의 변화를 판단하는 부분으로 간다.
> 맵 sky에 대해 sky가 비어있다면, 즉 어떤 높이정보도 없는, 빌딩이 다 끝난 상태면 0을 반환한다.
> 그게 아니면 맵은 key가 오름차순 정렬되므로 r.begin()->first로 맨 뒤의 key값(높이)을 잡아온다.
> 이 nHeight의 값이 전 과정에서 저장됐던 높이와 다르면, 높이가 변했다느 뜻이므로 Height를 갱신해주고 아니면 넘어간다.
> 갱신해주면서 해당 좌표와 높이를 출력해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
int N;
struct cmp
{
bool operator()(pair<int, int>a, pair<int, int> b)
{
if (a.first == b.first) return a.second < b.second;
return a.first > b.first;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
map<int, int> sky;
while (N--)
{
int L, H, R;
cin >> L >> H >> R;
pq.push({ L, H });
pq.push({ R, -H });
}
int Height = 0;
while (!pq.empty())
{
int fL = pq.top().first;
while (!pq.empty() && pq.top().first == fL)
{
int fH = pq.top().second;
pq.pop();
if (fH > 0) sky[fH]++;
else
{
fH = abs(fH);
sky[fH]--;
if (sky[fH] == 0) sky.erase(fH);
}
}
int nHeight = sky.empty() ? 0 : sky.rbegin()->first; //map이 비어있으면 높이0, 아니면 젤 높은거
if (Height != nHeight)
{
cout << fL << " " << nHeight << " ";
Height = nHeight;
}
}
}
후기
문제푸는 방법을 구상하는데 하루를 통으로 썼다. 진짜 감도안잡히고 죽는줄 알았다. 그래도 계속 생각하다보니 높이를 map으로 마킹해야겠다가 떠올랐고, 시작과 끝 처리도 맵의 증감으로, 또 erase로 높이 후보들 잡는거 등등 구상을 해냈다.
근데 마지막 문제로 똑같은 x좌표들에 대해 처리하는 게 발목을 잡았다. 어렵다.
