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

문제

https://www.acmicpc.net/problem/1863

1863번: 스카이라인 쉬운거

 

 

사용한 알고리즘

2022.01.27 - [PS/Algorithm] - [알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱)

-> 스택

2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디

 

 

풀이 

스카이라인의 고도가 바뀌는 지점의 y좌표에만 관심을 가지면 된다.
y좌표가 이전보다 작아질 때마다 건물 개수를 세어주면 된다.

1. 건물의 y좌표들을 순서대로 push해줄 stack을 만들어준다.
2. 스택이 비어있지 않고 top이 현재 y보다 크다면 건물개수를 증가시키고 pop을 한다.
   top과 y가 같다면 pop만 해준다.
3. 스택에 현재 y값을 push한다.
4. 위의 과정 반복이 끝난 후, 스택에 남아있을 건물도 세기위해 마지막에 y=0을 넣어주며 2번 과정을 한번 더 한다.
5. 건물 개수를 출력한다.

 

 

 

소스코드

#include <iostream>
#include <cstring>
#include <vector>
#include <stack>

typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n,ans=0; cin>>n;
    stack <int> st;
    for(int i=0; i<=n; i++){
        int x,y;
        if(i!=n) cin>>x>>y; //y에만 관심있음
        else y=0; // 마지막에 0넣어줌

        while(!st.empty()&&st.top()>=y){
            if(st.top()!=y) ans++;
            st.pop();
        }
        st.push(y);
    }
    cout<< ans;
    return 0;
}