백준_1863 : 스카이라인 쉬운거 - C++

문제

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

1863번: 스카이라인 쉬운거

---

문제 해석

- 밤에 태양이 질 때 보이는 건물의 윤곽을 스카이 라인이라 한다.

- 이 스카이 라인을 보고 건물이 최소 몇개 있는지 구하는 문제이다.

- 예시로 아래처럼 윤곽이 보인다면 건물이 3개 존재 하는데 다음과 같다.

..........
.....XX...
.XXX.XX...
XXXXXXXXXX

..........
.....XX...
.XXX.XX...
1111111111

..........
.....XX...
.222.XX...
X222XXXXXX

..........
.....33...
.XXX.33...
XXXXX33XXX

---

문제 풀이

- 입력을 받을 때는 2가지 종류가 있다.

 . 건물이 커지는 경우

 . 건물이 작아지는 경우

 . 윤곽이 바뀔 때만 입력으로 들어 오기 때문에 동일 한 경우는 없다.

 

- 이 때 건물의 크기가 커지는 경우는 다른 건물로 봐도 무방 하지만 작아지는 경우는 무조건 다른 건물로 보기 힘들다.

 . 아래 그림을 보면 건물의 크기가 3 에서 2로 줄었지만 1번칸과 3번 칸의 건물이 같은 건물일 가능성이 있기 때문이다.

 . 또한 문제에서 건물 개수의 최소를 구하라고 하였기 때문에 이는 같은 건물로 보는 것이 옳다.

 . 반대로 아래 그림은 크기가 줄었지만 1번과 3칸은 다른 건물이다.

 . 건물의 높이가 다르기 때문이다.

 

- 즉 정리 하자면 입력 값에서 건물의 크기가 늘었다면 다른 건물, 줄었다면 이 전의 건물들과 비교해서 건물의 수를 확인 하면 된다.

 

- 여기서 한가지 주의 할 점이 있는데 윤곽이 0 도 입력 된다는 점이다.

 . 아래 그림에선 3번 칸은 2번칸에서 높이가 줄었고 1번 칸의 높이와도 다르지만 높이가 0 이기 때문에 건물로 생각 하면 안된다.

 

- 스택을 통해 구현 하고 위 조건을을 적용 시키면 문제를 해결 할 수 있다.

---

코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int N;
stack<int> s;
int ans = 0;

void solution(){
    cin >> N;
    while(N--){
        int x, y;
        cin >> x >> y;
        while(!s.empty() && s.top() > y){
            int del = s.top();
            s.pop();
            if(!s.empty() && s.top() == del) continue;
            if(del == 0) continue;
            ans += 1;
        }
        s.push(y);
        cout << s.size() << '\n';
    }

    while(!s.empty()){
        int tmp = s.top();
        s.pop();
        if(!s.empty() && s.top() == tmp) continue;
        if(tmp == 0) continue;
        ans += 1;
    }
    cout << ans << '\n';
}

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

    solution();
}