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

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

17298번: 오큰수

---

 문제 풀이

오큰수를 구하는 것 자체는 어렵지 않다. 하지만 이 문제에서 중요한 것은 시간 복잡도이다.

일반적인 for문을 구하면 시간 초과가 나서 스택을 활용해서 풀어야 한다.

스택의 LIFO를 이용하기 위해서 내림차순으로 쌓아준다. (Bottom은 최댓값, top은 최솟값)

스택의 top과 비교해서 arr [i] (입력받은 i번째 값) 보다 작다면 pop 해준다.

만약 스택이 비어있으면 '-1'을 저장해준다. (비어있는 경우 → 시작 혹은 arr [i]가 top보다 클 경우)

비어있지 않다면 배열 ans에 top이 오 큰 수이기 때문에 top을 저장해준다.

그리고 arr [i]를 스택에 push 해준다.

 느낀 점

시간 복잡도를 어떻게 조정해야 할지 많이 고민했다. 다른 분들의 코드를 봐도 전혀 이해가 가지 않았는데 역으로 시작하는 코드를 보고 단번에 이해할 수 있었다. 다음에 한 번 더 고민해봐야 할 문제인 것 같다.

 코드

#include <iostream>
#include <stack>

using namespace std;

int n;
stack<int> s;
int arr[1000001];
int ans[1000001];

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = n - 1; i >= 0;i--) {
		while (!s.empty() && s.top() <= arr[i]) s.pop();
		if (s.empty()) ans[i] = -1;
		else ans[i] = s.top();
		s.push(arr[i]);
	}

	for (int i = 0; i < n;i++) {
		cout << ans[i] << " ";
	}
}