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

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

17298번: 오큰수

 

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

풀이

얘는 좀 다른게 입력을 미리 받고 입력값들을 >뒤에서부터< 꺼내야 한다

그리고 꺼낸값을 스택에 집어넣으면 자연스럽게 스택에 있는 수들은 자신의 >오른쪽 수<가 됨

 

이제 스택에 있는 값이

자신보다 작다 -> 오큰수 조건에 안맞으므로 그냥 pop

자신보다 크다 -> 오큰수 조건에 맞으므로 출력가능

 

이때, 출력은 왼쪽부터 가야하므로 답들을 벡터에 저장하고

출력할때 해당 답벡터를 역으로 출력했다

 

// Authored by : seondal
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

stack <int> s;
vector <int> input;
vector <int> ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    // 입력
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    
    // 계산
    for(int i=n-1; i>=0; i--){
        while(!s.empty() && s.top() <= input[i]) {
            s.pop();
        }
        
        if(s.empty()) {
            ans.push_back(-1);
            s.push(input[i]);
            continue;
        }
        
        ans.push_back(s.top());
        s.push(input[i]);
    }
    
    // 출력
    for(int i=n-1; i>=0; i--){
        cout << ans[i] << " ";
    }
    
    return 0;
}

/*
 */