BOJ - 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)을 공백으로 구분해 출력한다.

예제 입력 1

4 3 5 2 7

예제 출력 1

5 7 7 -1

예제 입력 2

4 9 5 4 8

예제 출력 2

-1 8 8 -1

사용할 자료구조

• 가장 가까운 오른쪽에 있는 수 중에 하나를 골라야하므로(= 가장 최근값과 뭐가 더 큰지 비교를 해야하므로) 스택을 사용하여 구현하였습니다.

풀이 과정

1. 배열에 먼저 입력값을 받아 저장받습니다.

2. 배열의 입력받은 인덱스를 스택에 저장합니다 (이 때, 0번 인덱스에도 접근할 수 있어야하므로 미리 스택에 0도 함께 삽입해줍니다.)

3. stack.top()보다 큰 수가 나왔을 경우, top 의 원소의 오큰수는 그 수가 됩니다.

(스택의 원소들은 현재 내림 차순이므로, pop해도 다음 top 의 오큰수도 그 수가 되므로, top 원소가 그 수보다 클 때까지 반복해줍니다.)

1. 오큰수를 구했으면 답을 다른 벡터(answer)에 저장해줍니다. 그러나 만약, 스택에 남아있는 인덱스가 있다면 그 수는 오큰수를 찾지 못했다는 뜻이므로 해당 인덱스에 -1을 삽입해줍니다.

시간 복잡도

• 스택의 삽입/삭제 연산의 시간 복잡도는 O(1) 입니다.
• 모든 원소가 스택에 한번씩 push 되고, 한번씩 pop되므로 시간 복잡도는 O(N) + O(N) ⇒O(2N) = O(N) 입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    stack<int> s;
    vector<int> input(N);
    vector<int> answer(N);
    for(int i=0;i<N;i++){
        cin>>input[i];
    }
    s.push(0);
    for(int i=1;i<N;i++){
        if(s.empty()){
            s.push(i);//인덱스를 삽입
        }
        while(!s.empty() && input[s.top()] < input[i]){
            answer [s.top()] = input[i];
            //cout<<i<<":"<<s.top()<<" "<<answer[s.top()]<<'\n';
            s.pop();
        }
        s.push(i);//인덱스를 삽입
    }
    while(!s.empty()){
        answer[s.top()]=-1;
        s.pop();
    }
    for(int i=0;i<answer.size();i++){
        cout<<answer[i]<<' ';
    }
    return 0;
}