[c++] 백준 17298, 오큰수

백준 17298

🌲 문제 요약

수열의 각 원소에 대한 오큰수를 구하는 문제.

🌲 문제 풀이

스택 stk를 이용하여 문제를 해결한다. a[i]의 값을 입력받아 만약 stk의 내용이 존재하고, a[i]의 값이 a[stk.top()]의 값보다 크다면, ret[stk.top()]에 a[i]를 저장한다. 이후 i를 stk에 push한 뒤, 다음 인덱스에 대하여 같은 과정을 반복한다.

🌲 주의

stk에 인덱스 값이 아닌, 배열의 값을 넣지 않도록 주의한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int n, a[1000005], ret[1000005];
stack<int> stk;

int main() {
	cin >> n;
	memset(ret, -1, sizeof(ret));
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		while (stk.size() && a[stk.top()] < a[i]) {
			ret[stk.top()] = a[i];
			stk.pop();
		}
		stk.push(i);
	}
	for (int i = 0; i < n; i++) {
		cout << ret[i] << ' ';
	}
	cout << '\n';
	
	return 0;
}