[C++] 프로그래머스 탑 (스택/큐)

#include <string>
#include <vector>
#include <stack>
using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    stack<int> queue, temp;
    int i;
    
    for(i = 0; i<heights.size(); i++){
        while(true){
            if(temp.size()==0){
                answer.push_back(0);
                break;
            }
            if(heights[temp.top()] > heights[i]){
                answer.push_back(temp.top()+1);
                temp.pop();
                break;
            }
            else temp.pop();
        }
        queue.push(i);
        temp = queue; 
    }
    return answer;
}

그냥 벡터를 순회하면 된다고 생각했다. 근데 스택/큐 문제였고, height의 길이가 길어지면 시간복잡도가 엄청나게 커져 시간초과가 발생할 것이라고 했다. 그래서 이왕 푸는거 스택/큐를 사용하고 싶었다. 

 

heights의 0번부터 인덱스 값을 스택 queue에 담는다.

 

스택에 담기 전에 스택 temp 에 나보다 큰 수가 있으면 answer.push 한다.

나올 때 까지 temp.pop 한다. 

만약 temp 스택이 다 빌때가지 없으면 그냥 answer.push(0) 한다.

 

queue에 새로 값을 넣고 temp 스택도 갱신한다.

왜냐면 while문 안에서 temp는 계속 바뀌니까