[ 백준 ] 17298번 : 오큰수 - (CPP/C/C++)

• 문제

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

17298번: 오큰수

---

• 풀이법

중요 코드

while (!s.empty() && s.top() <= A[i]) s.pop();
if (!s.empty() && s.top() > A[i]) nge[i] = s.top();
s.push(A[i]);

 

인덱스를 거꾸로 돌며 스택에 수열 A의 값을 push 한다. 값을 push 하기 전에 스택의 top이 A [index]보다 작은 동안 스택 pop, 만약 스택의 top이 A [index]보다 크다면 정답 배열 nge [index]를 업데이트한다.

(nge 배열은 -1로 초기화되어 있다.)

---

 

• 풀이

#include <iostream>
#include <stack>

using namespace std;

int n;
int A[1000001], nge[1000001];
stack <int> s;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	//수열 입력
	for (int i = 0; i < n; i++) cin >> A[i];
	for (int i = 0; i < n; i++) nge[i] = -1;

	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() && s.top() <= A[i]) s.pop();
		
		if (!s.empty() && s.top() > A[i]) nge[i] = s.top();

		s.push(A[i]);
	}

	//정답 출력
	for (int i = 0; i < n; i++) cout << nge[i] << " ";
	return 0;
}