[백준/BOJ] 17298번 오큰수 (C++)

www.acmicpc.net/problem/17298

17298번: 오큰수

스택 유형의 문제

프로그래머스의 주식가격과 비슷한 문제였습니다. 인덱스 번호를 스택에 넣어주면서 스택의 top을 인덱스로하는 벡터의 값과 현재 인덱스의 벡터의 값을 비교하여 오큰수를 찾아내는 것이 포인트입니다. 비교가 끝난 후, 스택에 남아있는 인덱스 번호는 만족하는 오큰수를 가지지 않으므로 따로 -1을 대입하면 됩니다.

 

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
	cin >> n;
	vector<int> v(n), answer(n);
	stack<int> s;
	
	for(int i = 0; i < n; i++) {
		cin >> v[i];
	} 
	
	for(int i = 0; i < n; i++) {
		while(!s.empty() && v[s.top()] < v[i]) {
			answer[s.top()] = v[i];
			s.pop();
		}
		s.push(i);
	}

    // 스택에 남아 있는 인덱스는 만족하는 오큰수가 없음
	while(!s.empty()) {
		answer[s.top()] = -1;
		s.pop();
	}
	
	for(int i = 0; i < n; i++) {
		cout << answer[i] << " ";
	}
}