[BOJ] 22866번 : 탑 보기 C++ 풀이

스택으로 해결할 수 있는 문제이다. 현재 건물의 높이를 기준으로, 왼 오른쪽을 전부 바라봤을때 볼 수 있는 건물의 개수를 세라고 한다. 앞에서 부터 값을 저장한 스택과 뒤에서 부터 값을 저장한 스택을 사용하면 각 칸별로 바라볼 수 있는 건물의 개수를 구할 수 있다.

그다음 구해야 하는 것은 가장 가까운 건물의 번호이다.
가까운 건물의 번호는 스택으로 볼 수 있는 건물을 셀때 약간의 조건문을 통해 갱신하면 된다는 것을 쉽게 알아챌 수 있다. 스택을 갱신할 때마다 건물과 거리를 갱신하자. 그리고 이 번호가 갱신되는 순간 건물의 번호를 갱신해주면 된다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 100010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

int N, cnt[NUM], mini[NUM], dist[NUM];
vector<pii> v1, v2;
stack<pii> s;

void init() {
    memset(cnt, 0, sizeof(cnt)); 
    cin >> N;
    for (int i=0; i<N; i++) {
        int x;
        cin >> x;
        v1.push_back({x, i+1});
        v2.push_back({x, i+1});
        mini[i] = INF;
        dist[i] = INF;
    }
    reverse(v2.begin(), v2.end());

    for (int i=0; i<N; i++) {
        int num = v1[i].X;
        while (!s.empty()) {
            int t = s.top().X;
            if (t <= num) {
                s.pop();
            } else {
                if (dist[i] > i+1 - s.top().Y) {
                    mini[i] = s.top().Y;
                    dist[i] = i+1 - s.top().Y;
                }
                break;
            }
        }
        cnt[i] += s.size();
        s.push({num, v1[i].Y});
    }
    while (!s.empty()) s.pop();
    
    for (int i=0; i<N; i++) {
        int num = v2[i].X;
        while (!s.empty()) {
            int t = s.top().X;
            if (t <= num) {
                s.pop();
            } else {
                if (dist[N-1-i] > s.top().Y - (N-i)) {
                    mini[N-1-i] = s.top().Y;
                    dist[N-1-i] = s.top().Y - (N-i);
                }
                break;
            }
        }
        cnt[N-1-i] += s.size();
        s.push({num, v2[i].Y});
    }

    for (int i=0; i<v1.size(); i++) {
        if (cnt[i] == 0) {
            cout << 0 << '\n';
        } else {
            cout << cnt[i] << " " << mini[i] << '\n';
        }
    }
}       

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}