17298번 (gold 4)

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

N의 크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과하기 때문에 다른 방법을 사용해야 하는데, stack의 선입후출의 특성을 이용하여 풀어보았다.

 

#include <iostream>
#include <stack>
#include <vector>

using namespace std;
typedef pair<int, int> node;
int main() {
	int N;
	cin >> N;
	stack<node> st;
	//int* arr = new int[1000001] {};
	vector<int> arr(N + 1, 0);
	for (int i = 1; i <= N; ++i) {
		int tmp;
		cin >> tmp;
		while (true) {
			if (st.empty()) {
				st.push(node(i, tmp));
				break;
			}

			if (st.top().second < tmp) {
				arr[st.top().first] = tmp;
				st.pop();
			}
			else if (st.top().second >= tmp) {
				st.push(node(i, tmp));
				break;
			}
		}
	}


	for (int i = 1; i <= N; ++i) {
		if (arr[i] == 0) arr[i] = -1;
		cout << arr[i] << " ";
	}

	//delete[] arr;

	return 0;
}