[백준 1863] 스카이라인 쉬운거 (C++)

1863번: 스카이라인 쉬운거

 

스택

 

높이가 바뀌는 y좌표만 저장하면 된다.

높이가 점점 증가하다가 갑자기 감소했을 때, while문을 돌면서 stack의 top에 위치한 높이가 현재 높이와 같거나 작아질 때까지 pop을 수행한다. 

 

마지막에 stack에 남아있는 건물의 수 만큼 답에 더해준다.

 

 

#include <iostream>
#include <vector>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;
 
int N;
vector<int> height;
vector<int> stk;
 
void input(){
    cin >> N;
    int x, y;
    for(int i = 0; i < N; i++){
        cin >> x >> y;
        height.push_back(y);
    }
}
 
void solve(){
    int cnt = 0;
    for(int i = 0; i < N; i++){
        int now = height[i];
        while(!stk.empty() && stk.back() > now){
            if(stk.back()) cnt++;
            stk.pop_back();
        }
        if(!stk.empty() && stk.back() == now) continue;
        
        stk.push_back(now);
    }
    while(!stk.empty()){
        if(stk.back()) cnt++;
        stk.pop_back();
    }
    cout << cnt;
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}