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

리뷰

 

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

스택을 활용해 건물이 최소한 몇 채 인지를 구해 출력하는 문제

 

 

전역 변수

• n : 건물의 개수를 저장할 변수
• stack : 스택으로 활용하기 위한 벡터

 

함수

없음

 

 

문제풀이

1. n을 입력 받고, 변수 ans를 초기값 0으로 초기화한다.
2. n개의 고도가 바뀌는 지점의 좌표를 변수 x, y에 각각 입력 받는다.
3. 스택이 비지 않았고, 스택의 맨 뒤가 y이상일 경우를 조건으로 하는 while루프를 수행한다.
4. 스택의 맨 뒤가 y보다 클 경우 ans를 증가시킨다. 스택의 맨 뒤 요소를 빼내어 준다.
5. y가 0보다 클 경우 stack에 push해준다.
6. while문이 종료된 후 stack의 size를 ans에 더해준다.
7. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 0인 경우엔 stack에 push해줄 필요가 없다.

 

정답 코드

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

int n;
vector<int> stack;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	int ans = 0;
	while (n--) {
		int x, y; cin >> x >> y;
		while (!stack.empty() && stack.back() >= y) {
			if (stack.back() > y) ans++;
			stack.pop_back();
		}
		if (y) stack.push_back(y);
	}
	ans += stack.size();
	cout << ans;
}