[스택] 백준 17298번 오큰수

17298번

오큰수

스택을 사용하는 문제라는 것을 미리 알지 못했다면 풀기 어려웠을 것 같다.

들어오는 수열을 차례대로 스택에 넣는다. 새로 숫자가 들어오면, 스택의 top 과 비교해 더 큰지 아닌지를 판별한다. 스택은 오큰수가 아직 정해지지 않은 숫자들이 들어가는 곳이 된다.

1. stack의 top이 새로 들어온 숫자보다 작은 경우 :

   새로 들어온 숫자가 stack의 top의 오큰수가 된다.

2. stack의 top이 새로 들어온 숫자보다 같거나 큰 경우

   오큰수가 아직 정해지지 않은 상태이므로 스택에 넣는다.

들어오는 순서대로 배열에 담아 순서를 기록한다.

오큰수는 따로 배열에 담아 관리한다.

다만 문제가, 수열 Ai 가 서로 다른 수들로만 구성되어 있지는 않다는 것이다. 따라서 같은 숫자에 오큰수가 두 번 혹은 그 이상 결정되는 상황을 피하기 위해 수열의 각 원소는 구조체로 담도록 하였다. 구조체 내에는 오큰수를 저장할 수 있는 벡터와 벡터의 값을 읽은 횟수를 저장할 수 있는 변수 count를 만들었다 .

#include <iostream>
#include <stack>
#include <vector>

using namespace std;
struct number{
    int count;
    vector<int> status;
}; 
int main(){
    int num;
    int cur;

    cin >> num;
    vector<int> order;
    vector<struct number> result(1000001);
    //vector<vector <int> > status;
    stack<int> operators;
    for(int i=0;i<num;i++){
        cin >>cur;
        result[cur].count=0;
        order.push_back(cur);
        if(operators.empty()){
            operators.push(cur);
         //   cout << "empty, pushed!" << endl;
        }
        else{
            if(operators.top()<cur){
             //   cout << "top is smaller than current\n";
            while(!operators.empty() && operators.top() < cur){
           //     cout << "selected" << endl;
         //       printf("%d's oks is %d\n", operators.top(),cur);
                result[operators.top()].status.push_back(cur);
         //       result[operators.top()].count++;
               //status[operators.top()] = cur; 
               operators.pop();
            }
       //     cout << "replaced" << endl;
            operators.push(cur);
            }
            else{
     //           cout << "no effect" << endl;
               operators.push(cur); 
            }
        }
    }
    while(!operators.empty()){
     //   printf("%d is not matched.\n",operators.top());
        result[operators.top()].status.push_back(-1);
        //result[operators.top()].count++;
        operators.pop();
    }
    for(int i=0;i<num;i++){
       //status 결과 출력해야함.
       //cout << "printing...\n";
//        cout << status[order[i]]<< " ";
        //printf("%d's count is %d ",order[i],result[order[i]].count);
        cout << result[order[i]].status[result[order[i]].count] << " ";
        result[order[i]].count++;
    }
}