백준, BOJ, 17298번 C++ [CPP]

 

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다.

 

 

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

 

---

 

이것은 그냥 뭐 생각대로 하기 쉽지 않다.

 

해보려 했는데..인덱스가 저장이 안되어서 정말 힘들었다.그래서 pair를 쓸까 하다가.그냥 스택 2개를 썼다.

 

인덱스를 이용해야 한다라는 생각을 하면 어렵지만 생각할 수 있는 문제라고 한다.한 번에 생각하기는 확실히 힘든 것 같다.

 

다른 사람과 풀이를 비교하지 않는 이유는원리는 같아서 그렇다.

 

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

using namespace std;

stack <int> num; // 숫자를 넣음
stack <int> stk; // 인덱스를 넣음
int N;

int arr[1000001];

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}


int main(){
    
    cin >> N;
    
    
    for(int i = 1; i<=N; i++){
        int a;
        cin >> a;
        
        //비어있으면 그냥 스택에 추가
        if(stk.empty()){
            stk.push(i);
            num.push(a);
        }else{
            //스택의 맨 위보다 작으면 그냥 추가
            if(num.top()>=a){
                stk.push(i);
                num.push(a);
                continue;
            }
            
            // 스택의 맨 위보다 클 경우 해당 되는 모든 인덱스에 대해 해당 값을 가져야함.
            //pop()을 하면서  스택의 top이 더 커질 때 까지 비교
            while(num.top()<a){
                num.pop();
                int x = stk.top();
                arr[x] = a;
                stk.pop();
                //스택이 비어있으면 멈춤.
                if(stk.empty())break;
            }
            //그 후 해당숫자는 스택에 추가
            stk.push(i);
            num.push(a);
            
        }
    }
    
    
    //만약 끝나고도 스택에 인덱스가 남아있다면 해당 숫자들은 
    //큰 수를 찾지 못한 것
    while(!stk.empty()){
        int x = stk.top();
        stk.pop();
        arr[x] = -1;
    }
    
    
    
    
    // 인덱스 순서대로 출력
    for(int i = 1; i<=N; i++){
        cout << arr[i] << " ";
    }
    
}