[C/C++] 백준 17298번 - 오큰수

✏️ 문제 링크

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

17298번: 오큰수

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

※ 스택을 이용해서 푸는 문제 ※

● 스택에 새로 들어오는 수가 top존재하는 수보다 크면 그 수는 오큰수가 된다

● 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다

● 스택이 채워져 있고 A[index] > A[top]라면 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장

● 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감

● 과정을 수열 길이만큼 반복한 다음 현재 다음 수열에 남아있는 인덱스에 -1을 저장

 

✏️ 문제 코드

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<int>A(N, 0);
	vector<int>res(N, 0);
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	stack<int>myStack;

	myStack.push(0);

	for (int i = 1; i < N; i++) {
		while (!myStack.empty() && A[myStack.top()] < A[i]) {
			res[myStack.top()] = A[i];
			myStack.pop();
		}
		myStack.push(i);
	}

	while (!myStack.empty()) {
		res[myStack.top()] = -1;
		myStack.pop();
	}

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