[백준] 22866 - 탑 보기

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

22866번: 탑 보기

 

원래 건물 높이를 다루는 문제는 스택 하나로 쉽게 풀 수 있다.

하지만, 이 문제는 현재 건물보다 높은 건물 모두(양쪽)를 구해야 하는 문제이다.

 

따라서 본인은 이 문제를 두 개의 스택을 이용해서 해결했다.

 

사실상 두 개의 스택이라고 해보았자, 인덱스만 바뀌는 거라서 크게 다를 게 없다.

그래서 왼쪽을 다루는 스택 l만 가지고 풀이를 해보겠다.

 

문제의 예시를 그림을 그려보자.

 

이러한 입력이 왼쪽부터 들어온다고 할 때, 스택을 어떻게 관리해야 할까?

 

맨 처음 입력에 3의 입력이 들어온다. 그러면 스택은 아래와 같이 된다.

 

그다음에는 7의 입력이 들어온다.

그런데 잘 생각을 해보면, 왼쪽에 존재하는 자신보다 높이가 큰 빌딩을 구하는데 이용되는 스택인데, 7의 입력이 들어온다면 높이 3의 빌딩은 의미가 없어진다. 왜냐하면 높이 7의 빌딩의 존재 때문에 이후의 모든 빌딩은 7 보다 작거나 같은 높이의 빌딩을 볼 수 없기 때문이다.

 

 

이 다음 1의 입력이 들어온다.

이 문제에서는 1보다 작은 입력이 없지만, 일단은 넣어두자.

 

 

이후 6, 3의 입력이 들어오게 되는데 6의 입력때문에 1의 빌딩은 의미가 없어지므로, 스택에서 pop() 된다.

 

 

이런 식으로 스택을 구성해가면 왼쪽에 현재 빌딩의 높이보다 큰 빌딩이 몇 개 있는지 구할 수 있다.

바로, 매 순간의 스택의 크기가 바로 해당한다.

 

오른쪽도 똑같이 구할 수 있다.

 

그런데 이 문제는 구해야 하는 값이 하나 더 있다.

바로 거리가 가장 가까운 건물 중 번호가 작은 건물이다.

 

이 부분은 바로 매 순간 스택의 top의 번호이다.

생각해보면, 스택에는 항상 가까운 순서대로 채워지고, 항상 현재 건물의 높이보다 큰 건물의 번호가 존재하기 때문이다.

 

구현은 다음과 같다.

 

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

stack<pair<int, int>> l, r;
pair<int, int> ans[100001];
int inp[100001];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		inp[i] = a;

		while (!l.empty() && a >= l.top().first)
		{
			l.pop();
		}
		if (!l.empty())
		{
			ans[i].second = l.top().second;
		}
		l.push({a, i});
		ans[l.top().second].first += l.size() - 1;
	}

	for (int i = n; i >= 1; i--)
	{

		while (!r.empty() && inp[i] >= r.top().first)
		{
			r.pop();
		}
		if (!r.empty())
		{
			if (ans[i].second == 0 || abs(i - ans[i].second) > abs(i - r.top().second))
				ans[i].second = r.top().second;
		}
		r.push({inp[i], i});
		ans[r.top().second].first += r.size() - 1;
	}

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