<백준알고리즘> 22866번 스택이용

매우 비슷한 유형의 문제
->이 문제 유형과 거의 흡사하여 금방 해결할 수 있었다.

백준22866번

접근 과정

1. 전에 푼 문제에서 이번엔 양쪽을 고려하여 접근하면 될거라고 생각했고 그러기 위해 인덱스가 1에서 시작하는 경우와 N에서 시작하는 경우에 대해서 둘다 고려하고 그 경우 볼 수 있는 건물에 대한 수를 더해준다.

2. 볼 수 있는 건물중 현재 건물과 가장 가까운 건물을 출력한다.
   ->스택 top에 있는 건물의 번호는 왼쪽 그리고 오른쪽에서 각각 가장 가까운 건물이므로 이를 저장해주고 나중에 뭐가 더 가까운지 비교해주어 구현해주면 된다.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <deque>



using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0, 0, 1, -1 };


int N;

int height[100001] = { 0 };
int cnt[100001][3] = {0};


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

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

	stack<pair<int, int>> hs;

	hs.push({ height[1], 1 });


	for (int i = 2; i <= N; i++)
	{
		if (hs.top().first <= height[i])
		{
			int size = hs.size();

			for (int j = 0; j < size; j++)
			{
				int cur = hs.top().first;

				if (cur > height[i])
					break;

				hs.pop();
			}
		}

		if (hs.size() != 0)
		{
			cnt[i][0] = cnt[i][0] + hs.size();
			cnt[i][1] = hs.top().second;
		}

		hs.push({ height[i],i });
	}

	int size = hs.size();

	for (int j = 0; j < size; j++)
	{
		hs.pop();
	}

	hs.push({ height[N], N });


	for (int i = N-1; i >= 1; i--)
	{
		if (hs.top().first <= height[i])
		{
			int size = hs.size();

			for (int j = 0; j < size; j++)
			{
				int cur = hs.top().first;

				if (cur > height[i])
					break;

				hs.pop();
			}
		}

		if (hs.size() != 0)
		{
			cnt[i][0] = cnt[i][0] + hs.size();
			cnt[i][2] = hs.top().second;
		}

		hs.push({ height[i],i });
	}



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

			if (cnt[i][2] < 1)
				cnt[i][2] = 1e9;

			int n1 = abs(i - cnt[i][1]);
			int n2 = abs(i - cnt[i][2]);

			if (n1 > n2)
			{
				cout << cnt[i][0] << " " << cnt[i][2] << "\n";
			}
			else 
			{
				cout << cnt[i][0] << " " << cnt[i][1] << "\n";
			}
		
		}

	}

	return 0;
}