이번 문제는 백준의 골드 4 문제 스카이라인 쉬운거 문제다.
문제를 차근차근 읽어보자.
고도가 바뀌는 지점의 x좌표와 고도가 주어진다.
이 때, 건물의 형태(스카이라인)을 보고 몇개의 빌딩인지 세어보자.
건물은 모두 밋밋한 직사각형의 형태인 점도 주목하자.
제약조건은, 지점은 최대 50000개가 주어질 수 있다.
50000개의 지점을 훑는데에는 그렇게 시간이 오래 걸리지 않을 것 같다.
스택의 이용
그럼 이제 어떻게 풀 것인가?
고도가 바뀔 때, 이게 어느 건물의 스카이라인인지 어떻게 구분할까?
동일한 고도일 때는, 같은 건물이라고 생각할 수 있을 것 같다.
이 때, 더 낮은 고도의 스카이라인이 등장하면 건물의 끝을 의미하게 된다.
즉 높은 고도의 스카이라인이 등장하면 해당 건물을 새 건물로 세어주고,
더 낮은 고도의 스카이라인이 등장하면 해당 건물은 끝났다고 생각하면 된다.
이걸 코드로 구현하려면, 스택이 가장 적합할 것 같다.
왜? 스택의 top에 있는 건물의 높이와 비교해서 넣고 빼고를 할 수 있기 때문이다.
더 낮은 고도의 스카이라인이 등장하면 정답을 추가하고 스택에서 빼고,
동일한 고도의 스카이라인이 등장하면 추가 없이 그냥 뺀다.
그 외의 다른 경우에는 그냥 스택에 고도를 삽입하기만 하도록 하자.
그런데 잠깐 고민이 되는 부분이 있다.
마지막에 낮은 고도의 스카이라인이 나오지 않으면,
미쳐 빠져나오지 못한 건물들이 스택에 아직 남아있게 된다.
일단 이 부분은, 위의 과정을 한 번 더 돌림으로써 해결해 놓았다.
좀 더 깔끔하게 코드를 짤 수 있는 방법도 있을 것 같은데,
아직 생각이 나지 않는다.
#include <iostream>
#include <stack>
using namespace std;
int num = 0, st_x = 0, height = 0, answer = 0;
stack<int> skyline;
int main() {
cin >> num;
for (int i = 0; i < num; i++) {
cin >> st_x >> height;
while (!skyline.empty() && skyline.top() >= height) {
if (skyline.top() > height)
answer++;
// 뺄 때 건물에 추가해 줌
// 왜? 해당 건물보다 작은 건물이 나오면
// 건물이 끝났다는 말이기 때문!
skyline.pop();
}
skyline.push(height);
}
height = 0;
while (!skyline.empty() && skyline.top() >= height) {
if (skyline.top() > height)
answer++;
skyline.pop();
}
cout << answer++;
return 0;
}