<백준 알고리즘>스택 이용 2493번 문제

백준 2493번

접근 과정

1. 탑마다 반복문을 돌며 처음으로 자신보다 높은 것이 있는지 찾는 방법이 있는데 이러면 시간복잡도가 O(n^2)이 나올 것 이므로 다른 방법을 찾기로 함.

2. 다음으로 해본 생각은 어차피 6 2 3 9 2 5의 형태일 경우 9이후부턴 9가 제일 높으므로 다른 탑에는 도달하지 못하니까 9의 앞부분은 없다고 생각하는 방식으로 접근 해야겠다고 생각함.

3. 스택을 이용하여 2번 방식으로 도달할 수 있는 탑만 담는 방식을 이용해야 겠다고 생각함. 예를 들어 4 2 6 3 2 7 6 일 경우 처음엔 스택에 4를 넣고 시작한다. 그 다음 2를 넣고 만약 6일 경우 스택의 top 높이 보다 크니까 6보다 높은 수가 나올 때까지 pop을 해준다 이 경우엔 없으므로 스택을 비워주고 6을 push해준다. 다음엔 3 2 를 넣고 7은 같은 방식으로 하면 모두 pop이 되고 7만 push해준다.

이런 방식으로 했을 때 만약 top보다 높이가 낮을 경우 무조건 top에서 만나므로 그것이 만나는 곳이 되고 만약 스택이 비어있을 경우엔 자기가 제일 높은 높이라는 뜻이므로 0을 출력해주면 된다.

#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 tops[500001] = { 0 };


stack <pair<int,int>> tp;

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

	cin >> N;


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

	tp.push({tops[1], 1});


	int ans = 0;

	for (int i = 1; i <= N; i++)
	{

		if (i == 1)
		{
			ans = 0;
			cout << ans << ' ';
			continue;
		}

		if (tp.top().first < tops[i])
		{
			int size = tp.size();

			for (int j = 0; j < size; j++) //자기보다 높은 높이가 나올때까지 pop해줌
			{
				int height = tp.top().first;
				if (height < tops[i])
				{
					tp.pop();
				}
			}
		}

		if (tp.size() == 0) //스택이 비어있을 때 = 자기가 가장 높은 경우이므로 0을 출력
			cout << 0 << ' ';
		else
			cout << tp.top().second << ' '; //스택의 top값은 자기보다 높은 높이이므로 = 가장 먼저 만나는 탑이므로 이 값을 출력

		tp.push({tops[i],i});

		
	}




	return 0;
}