[백준] 알고리즘 C++ 17298번 - 오큰수 문제

문제

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

17298번: 오큰수

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <math.h>
#include <stack>
using namespace std;
stack<int> st;
int arr[1000001];
vector<int> ans;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for (int i = n; i > 0; i--) {
		while (!st.empty() && st.top() <= arr[i]) {
			st.pop();
		}
		if (st.empty()) ans.push_back(-1);
		else ans.push_back(st.top());

		st.push(arr[i]);
	}
	for (int i = ans.size() - 1; i >= 0; i--) {
		cout << ans[i] << " ";
	}
}

해설

2중 포문을 사용하게 되면 O(N^2) 시간초과가 날게 뻔한 문제이다.

O(N)으로 문제를 해결해보기 위해 스택을 이용해보자.

스택의 힌트는 오큰수는 오른쪽에 있으면서 A번째 보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.

이말의 의미는 매번 A번째 숫자를 기준으로 오른쪽으로 탐색할 것인데 이게 A보다 큰 수를 찾아내야 한다는 것이다. 하지만 큰 수 중에서 가장 왼쪽에 있는 수를 의미 한다는 말을 조금 생각해보면 스택의 가장 윗 부분과 A를 비교하여 스택의 윗 부분이 크면 A를 다시 스택에 넣어 준다는 의미이다.

 

즉 오큰수를 찾은 후 자기자신을 스택에 넣음으로써 그다음 수인 A보다 스택의 탑이 클 경우 이 숫자가 오큰수가 되기때문이에 스택을 이용하면 야무지게 문제를 해결할 수 있다.