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

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

1863번: 스카이라인 쉬운거

처음보면 문제가 무슨 말인지 알아먹기가 힘들다. 문제를 풀긴 했지만 문제 뜻을 정확히 이해하고 푼건 아니고, 예시를 보고 했다.

구하라는 것은 스카이라인 좌표를 보고 최소 건물의 개수를 구하라는 것이다.

푸는 방법은 이전에 포스팅 했던 오큰수하고 비슷하다.(거의 똑같음)

 

x좌표는 필요없어서 안썼고, y좌표의 높낮이가 중요한데 y좌표를 입력받고 stack에 넣는다. 이때 다음 y좌표가 스택에 있는 y좌표들 보다 작으면 y보다 작은 스택에 있는 모든 숫자들을 제거해준다.(== 건물의 개수)여기서 주의해야할 것은 연속으로 같은 숫자가 pop되면 그것은 같은 건물이기에 count를 잘 조절해줘야한다.또 y좌표가 0이면 건물이 없는 것이므로, y좌표가 나올시 count를 미리 하나 빼줘야한다.코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#define endl "\n"

using namespace std;
int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int n,x,y,cnt = 0;
  cin >> n;
  stack<int> stack;
  set<int> set;
  for(int i = 0; i < n; i++){
    cin >> x >> y;
    while(!stack.empty() && y < stack.top()){
      int tmp = stack.top();
      stack.pop();
      cnt++;
      if(!stack.empty() && y < stack.top()){
        int tmpp = stack.top();
        if(tmp == tmpp) cnt--;
      }
    }
    stack.push(y);
  }
  int stack_size = stack.size();
  for(int i = 0; i < stack_size; i++){
    if(stack.top() != 0){
      set.insert(stack.top());
    }
    stack.pop();
  }
  int ans = cnt + set.size();
  cout << ans;
}

 

 

오큰수를 풀었어서 그런지 쉽게 풀었다.