[백준 C++] 17298번: 오큰수

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

17298번: 오큰수

 

처음 골드문제? 인거같다.

 

이중 포문으로 쉽게 풀 수 있을줄 알았지만 시간초과가 생겼다. O(n^2)인데 n이 1000000이여서 

 

따라서 스택으로 풀었다.

 

또한 풀다가 C6262 에러코드가 떠서 실행이 안되었는데 이는 main함수의 데이터를 초과하여 발생한 오류로 1000001이라는 int형 배열의 크기가 너무 커서 이를 전역변수로 선언해 주어 해결하였다.

 

#include <iostream>
#include <stack>
using namespace std;
int a[1000001];
int ans[1000001];
stack<int> s;
int n;
int main() {
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
	
	for (int i = n - 1; i >= 0; i--)
	{
		while (!s.empty() && s.top() <= a[i])
			s.pop();
 
		if (s.empty())
			ans[i] = -1;
		else 
			ans[i] = s.top();
		
		s.push(a[i]);
	}
 
	for (int i = 0; i < n; i++)
		cout << ans[i] << " ";
 
	return 0;
}

 

뒤에서 부터 정답값을 넣어주기 때문에 작은 수만 있으면 되고 큰수는 필요없다.