백준 1863번: 스카이라인 쉬운거

 

풀이

 문제 제목을 '안 쉬운 거'로 바꿔야 한다.

 힌트를 보면 이것 역시 스택 문제라는 걸 알 수 있다. 현재 입력된 빌딩 고도보다 더 높은 빌딩들을 스택에서 제거하고 결과값을 하나씩 증가하면 된다. 입력된 빌딩과 같은 고도의 빌딩이 이미 스택에 있다면, 같은 빌딩이라는 뜻이기 때문에 스택에 push할 필요가 없다. 마지막으로 반복문이 끝난 후에 스택에 남아있는 빌딩 개수만큼 결과값을 증가시키도록 한다. 

 

 

코드

#include <iostream>
#include <stack>

using namespace std;

typedef struct point {
	int x; int y;
};

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int n, x, y, cnt = 0;
point p;
stack<point> s;

void solve(point p) {
	while (!s.empty() && p.y < s.top().y) {
		cnt++;
		s.pop();
	}
	if (!s.empty() && s.top().y == p.y) {}
	else s.push(p);
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> p.x >> p.y;
		solve(p);
	}

	while (!s.empty()) {
		if (s.top().y > 0) cnt++;
		s.pop();
	}
	cout << cnt;
}