[프로그래머스]스택/큐 : 탑 (level 2) (c++)

https://programmers.co.kr/learn/courses/30/lessons/42588

프로그래머스

 

 

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
vector<int> solution(vector<int> heights) {
    
    // 스택: 자기보다 더 작은 탑을 아직 찾지 못한 탑 idx
    stack<int> s;
 
    vector<int> answer(heights.size(), 0);
    for (int i = 0; i < heights.size(); i++)
    {
        // 스택 top 높이 <= i 높이 --> 스택 pop
        while (!s.empty() && heights[s.top()] <= heights[i])
        {
            s.pop();
        }
 
        // 스택 top 높이 > i 높이 --> 답 벡터 입력
        if (!s.empty() && heights[s.top()] > heights[i])
        {
            answer[i] = s.top() + 1;
        }
        
        s.push(i);
    }
 
    return answer;
}

 

스택 기준만 잘 잡으면 깔끔하게 풀린다