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

문제

백준 1863번 https://www.acmicpc.net/problem/1863

1863번: 스카이라인 쉬운거

코드

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

int n;
stack<int> s;

int main() {
	cin >> n;
	int cnt = 0;
	s.push(0);
    
	for(int i=0; i<n; i++){
		int a, b;
		cin >> a>>b;

		if (s.top() < b) {
			s.push(b);
		}
		else {
			while (s.top() > b) {
				cnt++;
				s.pop();
			}
			if(s.top()!=b)
				s.push(b);
		}	
	}
	while (!s.empty()) {
		cnt++;
		s.pop();
	}
	cout << cnt-1;
}

풀이방법

x좌표는 사실 의미가 없고, y좌표의 변화만 보기 때문에 스택을 이용한다. 스카이라인의 건물 최고 높이가 낮아지면 건물 하나가 끝났단 뜻이므고 높이가 낮아질 때마다 건물 개수를 센다.

입력값과의 높이비교를 위해 지표면의 높이인 0을 스택에 넣어준다. 그 뒤, 변화한 건물의 높이가 기존보다 높을 경우 해당 건물높이를 스택에 넣어주고, 기존보다 낮을 경우 해당 건물높이보다 높은 건물들을 모두 pop한 뒤, 해당 건물높이를 스택에 넣는다. 건물을 pop할 때마다 건물 개수를 세어준다. 마지막에 남은 건물들의 수를 세어주고, 0의 개수 한 개는 뺀다.

고민과정

마지막에 스택에 남아있는 건물들을 더해주는 것을 깜빡했었다.

너무 의식의 흐름 그대로 코드를 짠 것 같다. 뭔가 더 효율적인 구현방법이 있지 않을까?