[백준] 22866번: 탑 보기

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

22866번: 탑 보기

스택을 양쪽으로 쓰면 될 것 같다고 예상은 했으나 문제 풀이를 하는 데에는 어려웠다.

높은 빌딩에 가려지는 걸 구현하면 된다.

한 스택은 빌딩의 왼쪽을 비추고, 다른 한 스택은 빌딩의 오른쪽을 비춘다.

한 빌딩은 기준이고, 한 빌딩은 추가 여부를 고려해야하는 빌딩이다.

우선 두 빌딩보다 낮은 빌딩들은 앞으로 쭉 보여질 일이 없기 때문에, 모두 스택에서 제거한다.

그리고 만약 추가여부를 고려하는 빌딩이 기준 빌딩보다 낮으면 고려하지 않는다.

 

이렇게 스택을 정리한 뒤 스택의 top만 보고도 양 측으로 보이는 건물의 수와 가까운 건물의 번호를 알 수 있다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int N;
int main() {
	cin >> N;
	vector<pair<int,int>> answers(N, {0, 0});
	vector<int> buildings(N);
	stack<pair<int,int>> left;
	stack<pair<int,int>> right;

	for(int i = 0;i < N;i++) {
		cin >> buildings[i];
	}

	for(int i = 1;i < N;i++) {
		int l = buildings[i - 1];
		int cur_building = buildings[i];
		// 어차피 추후 보여질 수 없음
		int high = max(l, cur_building);
		while(!left.empty() && left.top().first <= high) {
			left.pop();
		}

		// 만약 현재의 빌딩보다 작으면 앞으로 쓰일 수도 없고 볼 수도 없음
		if(l > cur_building) {
			left.push({l, i});
		}
		answers[i].first = left.size();
		if(!left.empty()) {
			answers[i].second = left.top().second;
		}
	}

	for(int i = N - 2;i >= 0;i--) {
		int l = buildings[i + 1];
		int cur_building = buildings[i];
		int high = max(l, cur_building);
		while(!right.empty() && right.top().first <= high) {
			right.pop();
		}
		if(l > cur_building) {
			right.push({l , i + 2});
		}
		if(!right.empty()) {
			// 만약 앞전에 왼쪽에 보이는 건물이 없었던 경우
			if(answers[i].first == 0) {
				answers[i].second = right.top().second;
			}
			// 거리 계산 주의
			// i를 마음대로 0부터 시작하는 것으로 대체하면 안됨

			else if((i + 1) - answers[i].second > right.top().second - (i + 1)) {
				answers[i].second = right.top().second;
			}
		}
		answers[i].first += right.size();
	}

	for(int i = 0;i < N;i++) {
		if(answers[i].first == 0){
			cout << 0 << '\n';
		}
		else {
			cout << answers[i].first << " " << answers[i].second << '\n';
		}
	}

}