[백준] 2493-탑(C++)

문제링크:https://www.acmicpc.net/problem/2493

2493번: 탑

 

자료구조중에서 스택을 사용해야 하는 문제였습니다.

 

접근방식

 

1. 일반적인 방식을 생각한다면 최악의 경우에는 O(n^2)이 될수 있기 때문에 시간초과가 일어나는 것을 인지 

2. 항상 자신의 왼쪽에서 가까운 값들 부터 확인해야 한다는 아이디어를 통해서 스택을 사용하면 검색을 줄일 수있다는 것을 인지 

 

 

문제풀이 

 

1. 스택이 비어있다면 0을 출력

2. 스택에 값이 있다면, 스택의 top값이 현재 값보다 클때까지 pop!

3. 다시 1번을 수행한다.

 

아래는 정답코드입니다.

#include <iostream>
#include <stack>
using namespace std;
int n;
int arr[500000];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;

	stack <pair<int, int>> stk;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];

		if (stk.empty()) {
			stk.push(make_pair(i, arr[i]));
			cout << 0 << ' ';
		}
		else {
			
			while (!stk.empty()) {
				if (stk.top().second > arr[i]) {
					cout << stk.top().first << ' ';
					break;
				}
				else
					stk.pop();
				
			}

			if (stk.empty())
				cout << 0 << ' ';
			stk.push(make_pair(i, arr[i]));
		}

		
	}
	cout << "\n";


	return 0;
}