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

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

1863번: 스카이라인 쉬운거

 

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

int main() {
	int n;
	cin >> n;
	
	vector<int> v;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		v.push_back(b);
	}
	
	stack<int> st;
	int cnt = 0;
	for(int i = 0; i < n; i++){
		while(!st.empty() && v[i] < st.top()) {
			if(st.top() != 0) cnt++;
			st.pop();
		}
		if(!st.empty() && v[i] == st.top()) continue;
		st.push(v[i]);
	}
	while(!st.empty()){
		if(st.top() != 0) cnt++;
		st.pop();
	}
	cout << cnt << endl;
	return 0;
}

 

y좌표만 벡터에 저장한다.

 

벡터에 있는 값을 하나씩 돌며 스택에 push하는데

- 먼저 스택의 top에 위치한 높이가 현재 높이와 같거나 작아질 때까지 pop하고 cnt한다. 이 때 값이 0일 경우(건물이 아님) cnt하지 않는다.

- pop한 뒤 top에 위치한 높이가 현재 높이와 같을 경우 같은 건물이므로 push하지 않는다.

 

마지막에 stack에 남아있는 건물 수를 cnt에 더한다. 마찬가지로 0일 경우 더하지 않는다.