백준 22866 - 탑 보기

 

 

문제 설명

일직선으로 다양한 높이의 건물이 총 $N$개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.

 $i$번째 건물 기준으로 $i - 1$, $i - 2$, ..., $1$번째 건물은 왼쪽에, $i + 1$, $i + 2$, ..., $N$번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 $L$이라고 가정하면 높이가 $L$보다 큰 곳의 건물만 볼 수 있다.

바라보는 방향으로 높이가 $L$인 건물 뒤에 높이가 $L$이하인 건물이 있다면 가려져서 보이지 않는다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 건물의 높이가 주어진다.

특정 건물에서 볼 수 있는 건물은 자신의 높이보다 큰 건물들만 볼 수 있다.

각 건물이 볼 수 있는 건물의 개수와 가장 가까운 번호 중 작은 번호의 건물을 출력해야 한다.

 

해당 문제는 두 가지로 분해할 수 있다.

• 볼 수 있는 건물의 개수를 구하기
• 볼 수 있는 건물 중 가장 가까운 작은 번호의 건물 구하기

 

첫 번째 부분은 스택을 이용하여 해결할 수 있다.

스택은 자신의 이전 건물들 중 자신보다 높은 건물들이 유지되도록 관리해야 한다.

8
3 7 1 6 3 5 1 7

첫 번째 건물은 이전 건물이 없기 때문에 넘어가고 두 번째 건물은 첫 번째 건물의 높이가 3으로 자신보다 작기 때문에 스택에서 없앤다. 그러고 나서 모든 연산을 처리한 후 자신을 다시 스택에 넣는다.

이후, 높이가 1인 세 번째 건물은 현재 스택에 존재하는 높이가 7인 건물보다 작기 때문에 아무것도 하지 않는다.

이러한 방식으로 스택을 관리하면 스택에는 이전에 등장한 자신보다 큰 건물들만 존재할 것이다.

즉, 자신이 볼 수 있는 건물들이 스택에 존재하는 것이다.

 

하지만, 이는 반쪽짜리이다.

왼쪽과 오른쪽을 모두 진행해야 완전한 결과를 얻을 수 있다.

 

두 번째 부분인 가장 가까우면서 작은 건물의 번호를 알아내기 위해서는 진행과정 중 스택을 참조하여 구해낼 수 있다.

정답이 되는 건물의 번호를 기억하며 거리를 구해낼 수 있다.

만약, 스택이 비어있다면 볼 수 있는 건물이 없다는 뜻이기 때문에 넘어간다.

스택이 비어있지 않다면 스택의 탑에 있는 건물이 자신보다 크면서 가장 가까운 건물이 될 것이다.

따라서, 이를 계산해서 가장 가까운 볼 수 있는 건물을 구할 수 있다.

 

그렇다면 스택의 탑으로 모두 기록하면 된다 생각할 수 있다.

하지만, 그건 한쪽으로 진행하는 경우에만 적용된다.

왼쪽으로 진행할 때와 오른쪽으로 진행할 때 볼 수 있는 건물이 다르기 때문에 추가적인 조건으로 거리를 계산해서 업데이트해주어야 올바르게 동작한다.

if (!stack.empty())
{
    if (near[i] == 0)
    {
        near[i] = stack.back().first;
    }
    else if (abs(near[i] - i) > abs(stack.back().first - i))
    {
        near[i] = stack.back().first;
    }
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;

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

    cin >> N;
    vector<int> buildings(N + 1);
    vector<int> near(N + 1, 0);
    vector<int> cnt(N + 1, 0);
    vector<pair<int,int>> stack;

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

    //left
    for (int i = 1; i <= N; i++)
    {
        while (!stack.empty() && stack.back().second <= buildings[i]) stack.pop_back();
        cnt[i] += stack.size();

        if (!stack.empty())
        {
            if (near[i] == 0)
            {
                near[i] = stack.back().first;
            }
            else if (abs(near[i] - i) > abs(stack.back().first - i))
            {
                near[i] = stack.back().first;
            }
        }

        stack.push_back({ i, buildings[i] });
    }

    stack.clear();

    //right
    for (int i = N; i > 0; i--)
    {
        while (!stack.empty() && stack.back().second <= buildings[i]) stack.pop_back();
        cnt[i] += stack.size();

        if (!stack.empty())
        {
            if (near[i] == 0)
            {
                near[i] = stack.back().first;
            }
            else if (abs(near[i] - i) > abs(stack.back().first - i))
            {
                near[i] = stack.back().first;
            }
        }
        stack.push_back({ i, buildings[i] });
    }

    for (int i = 1; i <= N; i++)
    {
        if (cnt[i] == 0) cout << 0 << '\n';
        else cout << cnt[i] << ' ' << near[i] << '\n';
    }

    return 0;
}

---