[백준] C++ 풀이 22866번: 탑 보기 - 이게 스택이라고??

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

 

---

상당히 어렵게 풀었다..

각설하고 우선 완전탐색 풀이는 굉장히 쉽지만 n이 100,000이기에 불가능하다. n log n이나 n으로도 풀어야 한다. 한 번의 순회가 최대라는 것이다. (log n으로는 순회가 불가능하니 n log n이면 보통 한 번의 순회에서 log n짜리 처리를 하는 것)

 

이런저런 생각을 해보며 한 번의 순회로 어떻게 풀 수 있을까 고민을 해봤다. 일단 몇 가지 핵심 포인트를 찾았는데

1. 순회가 두 번은 일어나야 한다. n^2이 아니라 2n인 것. 왜냐하면, 한 번 스캔으로는 절대 모든 케이스를 찾을 수 없다. 왼쪽 -> 오른쪽 / 오른쪽 -> 왼쪽으로 잡아두자.
2. i번째 건물에서 딱 오른쪽 방향으로만 보이는 방향을 관찰하면 무언가 규칙이 있다.

오른쪽에서부터 순회하며 오른쪽 방향으로만 보이는 방향을 관찰해보자.

8번 건물 : X

7번 건물 : 8

6번 건물 : 8

5번 건물 : 6, 8 // 자신보다 6이 건물 높이가 높아서 바로 관찰할 수 있다.

4번 건물 : 8 // 기존 관찰 가능하던 6이 자신보다 높이가 낮아서 관찰할 수 없다. 여기서 한 가지 통찰을 얻었는데, 7번 건물은 한 번 관찰이 불가능하니 계속 불가능하다. 한 방향으로 제한했기에 규칙을 확정할 수 있다.

3번 건물 : 4, 8

2번 건물 : X

1번 건물 : 7

 

규칙을 좀 정리해보면

1. 한 번 관찰 불가능한 건물은 계속 불가능하다.
2. 한 번 관찰 가능한 건물은 그 건물보다 높은 건물이 나올때까지 계속 관찰 가능하다
3. 예를 들어 3번 건물에서 4번 건물이 관찰 가능해도 8번은 여전히 관찰이 가능하다. 즉, 새로운 관찰 가능한 건물이 등장해도 기존의 관찰 가능한 건물을 유지한다. 

이 규칙과 한 방향에서의 예시를 계속 보다보면 스택이 떠오른다. 한 방향으로만 삽입, 삭제가 일어나기에 그렇다.

특히 2번 건물을 보면 7보다 낮은 건물들을 제거해나가는 과정이 스택과 동일하다. 반대 방향도 똑같다.

 

우선 스택으로 잡아보고 자세히 알고리즘을 짜보자.

1. 오른쪽 -> 왼쪽 순회 (i=n-1 ~ 0)
2. i번째 건물이 i+1번째 건물보다 낮다면 -> 할 거 없음
3. i번째 건물이 i+1번째 건물보다 같거나 높다면 -> 오른쪽 방향으로 자신보다 낮은 건물들 제거

이렇게 정리하고 보니 스택이 확실하다. 한 방향이기에 그렇다. 이를 그냥 구현하면 된다. 

그리고 두 방향은 서로 전혀 간섭이나 충돌이 없다. 머리속으로 몇 번 굴리다보면 나온다.

 

/** 스택 22866 탑 보기 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;

stack<pair<int, int>> s1, s2; //{건물 번호, 높이}
int n;
int building[100010];
pair<int, int> ans[100010];

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

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> building[i];

    // 오른쪽 -> 왼쪽 순회
    // i번째 건물에서 오른쪽 방향으로 볼 수 있는 건물들
    // 7 x 4,8 8 6,8 8 x
    // 오른쪽에서부터 진행
    // i번째 건물이 i+1번째 건물보다 낮다면 -> continue
    // i번째 건물이 i+1번째 건물보다 같거나 높다면 -> 오른쪽 방향으로 자신보다 낮은 건물들 다 제거
    // 그냥 스택으로 하면 됨. 왜냐하면 한 방향으로만 삭제가 일어남
    int i;
    s1.push({n - 1, building[n - 1]});

    for (i = n - 2; i >= 0; i--)
    {
        if (building[i] >= building[i + 1])
            while (!s1.empty() && building[i] >= s1.top().second)
                s1.pop();

        ans[i].first += s1.size();
        if (!s1.empty())
            ans[i].second = s1.top().first;

        // if (!s1.empty())
        //     cout << s1.size() << ' ' << s1.top().first + 1 << '\n';
        // else
        //     cout << 0 << ' ' << 0 << '\n';

        s1.push({i, building[i]});
    }

    // 왼쪽 -> 오른쪽 순회 (왼쪽 방향으로 볼 수 있는 것들)
    s2.push({0, building[0]});

    for (i = 1; i < n; i++)
    {
        if (building[i] >= building[i - 1])
            while (!s2.empty() && building[i] >= s2.top().second)
                s2.pop();

        ans[i].first += s2.size();

        if (!s2.empty() && (ans[i].second == 0 || abs(ans[i].second - i) >= abs(i - s2.top().first)))
            ans[i].second = s2.top().first;

        // if (!s2.empty())
        //     cout << s2.size() << ' ' << s2.top().first + 1 << '\n';
        // else
        //     cout << 0 << ' ' << 0 << '\n';

        s2.push({i, building[i]});
    }
    for (int i = 0; i < n; i++)
        if (ans[i].first == 0)
            cout << 0 << '\n';
        else
            cout << ans[i].first << ' ' << ans[i].second + 1 << '\n';
}

/*
10만개의 건물에 대해 순회
i번째 건물의 좌우 중 자신보다 큰고 가까운 건물 출력
완전탐색 : n^2 -> 불가능
max : 높이 7 -> 높이 7인 건물은 답이 X



반대로 왼쪽 방향만 생각해보면
왼쪽에서부터 진행하면서 똑같이

*/