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

오늘은 백준17298번 오큰수 문제를 풀어보도록 하자.

스택문제로 N이 100만이라 하나하나씩 비교하면서 하면 O(N^2)이라 무조건 터지게 되어있다. 따라서 벡터에 값을 저장하고,

스택에 인덱스를 저장하며 접근해보았다.

문제는 다음과 같다.

                               [접근법]

  1. 벡터에 입력 값을 저장하고 맨 마지막엔 무조건 -1이니 -1까지 저장해준다.

  2. 스택에 벡터에 저장되어 있는 값의 인덱스를 저장해주는데 만일 스택이 비어있고 v[s.top()]의 값이 다음 값보다 크다면 push만하고 넘어간다.
  
  3. 만일 그렇지 않다면 ans 벡터에 하나씩 넣어주고 스택을 pop해주면 된다.

                                     [코드]
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

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

	int N, M;
	stack<int>s;
	vector<int>v, ans;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> M;
		v.push_back(M);
		ans.push_back(-1);
	}

	for (int i = 0; i < N; i++) {
		while (s.size() && v[i] > v[s.top()]) {
			ans[s.top()] = v[i];
			s.pop();
		}
		s.push(i);
	}
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}
	return 0;
}