스택/큐 - 탑

https://www.welcomekakao.com/learn/courses/30/lessons/42588

 

위 문제를 풀기 위해 아래 로직을 구현하였다.

그런데, 해당 문제의 범주가 스택/탑인데.. 내가 푼 방법은 사실 억지로 스택을 쓴 것 뿐이지 2중 for 문을 사용한 것과는 다를 것이 없다. 다른 사람의 코드를 아직 보진않았지만, 스택을 어떻게 써야 하는 문제인지 파악해보고 싶다.

1. 탑 index 와 탑의 높이를 stack 에 저장한다.
2. 저장 된 stack 을 pop 하면서 자신보다 앞에 있는 탑과 높이를 비교하며, 자신보다 높은 탑을 발견할 시 answer 에 push 
3. answer 에는 정답이 거꾸로 들어가있으므로 reverse 연산을 수행

 

#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
 
using namespace std;
 
vector<int> solution(vector<int> heights) {
    vector<int> answer;
    // pair -> [타워번호, 높이]
    stack<pair<int, int>> s;
    
    for (int i = 0; i < heights.size(); ++i) s.push({i, heights[i]});
    
    while (!s.empty()) {
        int curTop = s.top().first;
        int curTopHeight = s.top().second;
        bool getSignal = false;
        
        for (int i = curTop - 1; i >= 0; --i) {
            if (curTopHeight < heights[i]) {
                getSignal = true;
                answer.push_back(i + 1);
                break;
            }
        }
        
        if (!getSignal) answer.push_back(0);
        s.pop();
    }
    
    reverse(answer.begin(), answer.end());
    return answer;
}