[BOJ]백준 17928번: 오큰수/Stack

www.acmicpc.net/problem/17298

17298번: 오큰수

수열이 있을 때, 각 원소에 대해 오큰수를 구하는 문제

오큰수란? 해당 원소를 Ai라 할 때 Ai의 오른쪽에 위치한 원소들 중 index가 가장 작으면서 Ai보다 큰 원소를 나타낸다

 

예제에 대해, [3 5 2 7]을 마지막 원소부터 보면

- 7: 오른쪽에 원소가 없으므로 -1

- 2: 바로 오른쪽에 7이 2보다 크므로 7

- 5: 한 칸 건너뛰어서 7이 5보다 크므로 7

- 3: 7이 가장 크지만 5가 7보다 왼쪽에 있으므로 5

따라서 오큰수 수열은 [5, 7, 7, -1]이 된다

 

처음에는 수열을 처음부터 쭉 스택에 넣어주고 Ai보다 큰 수가 나올 때 까지 pop해주었는데,

그렇게 할 경우 [5 5 4 5 70]의 경우에서 정답인 [70 70 5 70 -1]이 아닌 [-1 -1 5 70 -1]을 출력해주었다

 

그렇기 때문에 현재 값보다 큰 max 변수 또한 stack으로 넣어줘서

stack의 top이 current보다 큰 원소가 나올 때 까지 pop해주면 된다

 

즉, [5 5 4 5 70]의 경우에서 70, 4, 5를 계산하고 난 뒤의 max 스택에는 [70 5]가 저장되어 있다

이 때, A2의 5를 검사하게 되면 max스택의 top인 5가 A2와 같으므로 pop해주고

다음 top인 70이 A2보다 크므로 A2의 오큰수가 된다

 

#include <cstdio>
#include <stack>
using namespace std;
stack<int> s,ans,m;
int n,arr[1000001];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		s.push(arr[i]);
	}

	m.push(-1);
	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() && (s.size() > i+1)) {
			if (s.top() > arr[i])
				m.push(s.top());
			s.pop();
		}
		while (!m.empty()&&m.top() <= arr[i])m.pop();
		if (!m.empty()&&m.top() > arr[i])
			ans.push(m.top());
		else ans.push(-1);
	}
	while (!ans.empty()) {
		printf("%d ", ans.top()); ans.pop();
	}
	return 0;
}