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

스택 문제입니다.

A의 수열이 있을 때
Ai의 오른쪽에는 경우 Ai+1 ~ Ai+n가 있습니다.
Ai+1 ~ Ai+n에서 Ai와 가장 가까운 Ai보다 큰 수를 구하면 됩니다.
없을 시에 -1을 출력합니다.

vecot v에는 입력 받은 값을 수열을 넣습니다.
vector ans에는 기본값 -1을 넣고 각 수열에 대한 오큰수의 값을 가집니다.
stack s에는 v[i]에 대한 i의 index를 넣습니다.

stack에는 오큰수를 확인 하지 못한 값들의 인덱스가 쌓이게 됩니다.
그리고 i를 증가하면서 stack에 쌓인 값들과 비교를 하면서
만약 v[i]가 더 크면 오큰수를 v[i]로 설정합니다.
이에 대한 값 설정은 ans배열에 넣습니다.

 

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

int main(int argc, char *argv[]) 
{ 
	int n; 
	int num;
	vector<int> v;
	stack<int> s;

	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		v.push_back(num);
	}
	
	vector<int> ans(v.size(), -1); 

	for (int i = 0; i < v.size(); i++) { 
		while (!s.empty() && v[s.top()] < v[i]) { 
			ans[s.top()] = v[i]; 
			s.pop(); 
		} 
		s.push(i); 
	} 

	for (int x : ans) {
		cout << x << " ";
	}
	
	return 0;
}