[c++]baekjoon 17298

www.acmicpc.net/problem/17298

www.youtube.com/watch?v=XwG-QcBQ9-I&t=716s

 

아래 문제를 브루터포스로 구현해서 제출을 하니 시간초과가 나와서 새로운 방법을 찾다가 우연히 유튜브에서 정답을 확인해서 아래와 같이 정리 했습니다.

 

psudo code

for(i =0; i <N; i++){
    while( stk.size() >0 && stk.top() < dt[i] ){
    
        오큰수 찾음;
        저장;
       }
   }

  1 #include <iostream>                                                                                                                                                                
  2 #include <stack>
  3 
  4 using namespace std;
  5 
  6 #define MAX 1000000
  7 int dt[MAX];    // input data
  8 int rlt[MAX];   // dt[i]의 오큰수는 rlt[i]에 저장 
  9 
 10 int main()
 11 {
 12     int n=0,i,j=0;
 13     int min =0;
 14 
 15     cin >> n ;
 16 
 17     stack<int> stkNotFound;     //오큰수를 아직 찾지 못한 수들 
 18     stack<int> stkNotFoundIdx;  //오큰수를 아직 찾지 못한 수들의 인덱스 
 19 
 20     for(int i =0; i < n; i++){
 21         cin >> dt[i];
 22     }
 23 
 24     for(int i =0; i < n; i++){
 25         int idx = i;
 26         cout << "stkNotFound.size : " << stkNotFound.size() << endl;
 27         //cout << "stkNotFound.top: " << stkNotFound.top() << endl;
 28     
 29         while (( stkNotFound.size() > 0 ) && ( stkNotFound.top() < dt[idx] )) {
 30             rlt[stkNotFoundIdx.top()] = dt[idx];
 31             stkNotFound.pop();
 32             stkNotFoundIdx.pop();
 33         }
 34 
 35         stkNotFound.push(dt[idx]);
 36         stkNotFoundIdx.push(idx);
 37             
 38     }
 39 
 40     while(stkNotFoundIdx.size() > 0 ){
 41         rlt[stkNotFoundIdx.top()] = -1;
 42         stkNotFoundIdx.pop();
 43     }
 44 
 45 
 46     //마지막 수의 오큰수는 항상 -1
 47     rlt[n-1] = -1;
 48 
 49 
 50     for( int i =0; i < n; i++) {
 51         cout << rlt[i] << ' ';
 52     }
 53 
 54     return 0;
 55 }