백준 2493 탑 c++

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

2493번: 탑

 이 문제는 프로그래머스 탑문제랑 같은 문제인것 같다

프로그래머스처럼 똑같이 이중 for문으로 풀었으나 시간초과로 실패했다..

컴파일 에러는  c++14로 해야하는데 c++로 선택해서 컴파일 에러가 난 것같다...

무튼 이문제는 그냥 다 stack으로 푸는 문제였다.

역시 프로그래머스 풀듯이 풀면 안되는거였는데..

무튼 !!

아이디어를 생각하는게 조금 어려웠다

 

   idea   

1. 처음 들어오는 애는 무조건 0을 출력해준다.

2. 그다음 스택에 index와 함께 들어오는 숫자(top_num)을 넣어준다.

3. 두번째부터 스택의 top에 있는 second(top_num)과 지금 들어온 top_num을 비교해준다.

4. 비교했을때 지금 들어온게 더 크면 어차피 다음 들어오는 것들은 지금 들어온 탑에 송신이 될것이므로 (가장 오른쪽에 있고 기존의 왼쪽 것들보다 크니까!) 지금 들어온것보다 작은 것들은 스택에서 pop을 해준다. 

5. 만약 이걸 다했는데 스택이 비어있다는건 지금 탑에서 나온 신호를 수신할 탑이 없다는 뜻이므로 0을 출력해준다.

6. 이걸 다 했는데 비어있지 않으면 그건 지금 탑에서 나온 신호를 현재 스택의 top()의 위치에 있는 것이 수신한다는 뜻이니 그 탑의 번호(first)를 출력해준다.

7.  4에서 비교했을때 만약 지금 들어온게 더 작다면 현재 스택의 top이 지금 탑에서 나오는 신호를 수신할 것이므로 현재 스택의 top을 출력한다.

8. 마지막으로 스택에 현재 top을 넣어준다.

반복..

#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main()
{
    int count;
    int top_num;
    int flag;
    cin >>count;
    vector<int> answer;
    stack<pair<int,int>> st;
    
    for(int i=0;i<count;i++){
        cin>>top_num;
        if(i==0){
            answer.push_back(0);
            st.push(make_pair(i+1,top_num));
        }
        else{
            if(top_num>st.top().second){
                //작은건 어차피 필요가 없으니까 계속 pop을 해줌
                while(!st.empty()&& top_num>st.top().second){
                     st.pop();
                }
                if(st.empty()){
                     answer.push_back(0);
                }
                else{
                    answer.push_back(st.top().first);
                }
            }
            else{
                answer.push_back(st.top().first);
            }     
            st.push(make_pair(i+1,top_num));
        }
    }
    
    
    for(int i=0;i<count;i++){
        cout<<answer[i];
        cout<<" ";
    }

    return 0;
}

솔직히 저 아이디어 생각하는게 어려웠다..다시 풀어봐야지