[Programmers] 탑 - travelbeeee

---

[ 알고리즘풀이 ]

■ 우리는 현재 탑에서 지금까지 순회한(왼쪽에 있는 탑들) 탑 중 나보다 높이가 큰 가장 가까운 탑을 고르면 된다.

- 왼쪽부터 순회하며 자료구조 Stack을 이용하면 문제를 간단히 해결할 수 있다.

- 현재 Stack이 비어있다면, 나보다 큰 탑이 없는 걸로 판단하고 answer에 '0', Stack에 현재 탑을 Push.

- Stack이 비어있지않다면, 나보다 큰 탑을 찾을 때까지 Stack을 Pop한다. 나보다 작은 탑들(Pop되는 탑들)은 어차피 나보다 작은 탑이라 앞으로 오른쪽 탑에서 보내는 수신 신호를 받지 못한다.

#include <string>
#include <stack>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    stack<pair<int, int>> s;
    for (int i = 0; i < heights.size(); i++) {
        while (!s.empty()) {
            if (s.top().first <= heights[i]) {
                s.pop();
            }
            else {
                answer.push_back(s.top().second);
                s.push({ heights[i], i + 1 });
                break;
            }
        }
        if (s.empty()) {
            answer.push_back(0);
            s.push({ heights[i], i + 1 });
        }
    }
    return answer;
}

---