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

📃 문제

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

1863번: 스카이라인 쉬운거

---

💻 코드

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

int N;
vector<int> v;
stack<int> s;
int cnt = 0;

int main() {
	cin >> N;

	int x, y; 
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		v.push_back(y);
	}
	v.push_back(0);

	for (int i = 0; i < v.size(); i++) {
		while (!s.empty() && s.top() >= v[i]) {
			if(s.top() > v[i])cnt++;
			s.pop();
		}
		s.push(v[i]);
	}
	cout << cnt << '\n';
}

 

메모리 및 시간

---

💡 풀이

- vector<int> v; // 좌표의 y값 저장

- stack<int> s; // 스카이라인 고도 오름차순으로 저장

 

 

1. 마지막 건물까지 확인하기 위해 입력 받은 y좌표 저장 후 0값을 마지막에 저장

    v.push_back(0);

 

2. 입력받은 y 좌표 만큼 (vector v의 크기) 반복

 

3. stack이 비어있지 않다면

     3-1. stack.top()이 현재 y좌표(v[i])보다 크거나 같으면 stack.pop()

     3-2. stack.top()이 현재 y좌표(v[i])보다 크면 건물 하나가 끝난 것이기 때문에 cnt(건물 개수)를 증가

     3-3. stack.top()보다 현재 y좌표(v[i])가 작으면 현재 y좌표를 stack에 push

     → stack에 오름차순으로 y좌표 값을 저장