[ 백준 17298 ] 오큰수 : C++ 풀이

나의 접근

이분탐색도 생각해보고, 뒤에서부터 진행도 생각해봤는데 도저히 감이 잡히질 않아서 주제를 봤더니 스택문제였습니다…

스택의 특징을 아직 잘 몰라서 실수를 했는데, 스택이 사용될 수 있는 상황은 다음과 같습니다.

• 현재 문제 상황이 선형적이지만, 여태까지 내가 “탐색”했던 정보들을 바탕으로 판단해야할 때,

• 혹은 탐색했지만 정답을 찾지못한 정보들을 모아두었다가 나중에 일괄적으로 문제를 해결할 수 있을 때,

• 그 외 느낌상으로 모아두었다가 해결할 수 있을 것 같을 때

한번 쯤 생각해보면 좋을 것 같습니다. 스택..실제로 활용 문제를 실전풀이로 할 때 상당히 어려운 것 같습니다.

알고리즘

1. 현재 수를 보고 다음 수를 본다, 다음 수가 더 크다면, 기본적으로 현재 수의 NGE는 다음 수이다.

2. 만약 다음 수가 더 작다면, 현재수를 push 하고 다음 수를 본다.

3. 1의 과정 중, 다음 수가 현재수보다 크다면, 현재 수의 NGE는 다음 수 이다, 또한 스택이 비지 않았을 때, top이 현재 시점의 다음 수보다 작을 경우, 해당 수의 NGE도 현재 시점의 다음 수이다.

소스코드

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

int main() {
	cout.tie(0); cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	vector<int> arr(n);
	vector<int> ans(n, -1);
	stack<int> st;

	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	
	for (int i = 0; i < n - 1; ++i) {
		if (arr[i + 1] > arr[i]) {
			ans[i] = arr[i + 1];
			while (!st.empty() && arr[st.top()] < arr[i + 1]) {
				ans[st.top()] = arr[i + 1];
				st.pop();
			}
		}
		else if (arr[i + 1] <= arr[i]) {
			st.push(i);
		}
	}
	for (int t : ans) {
		cout << t << ' ';
	}
}