[BOJ - 2493] 탑(C++)

  문제

 

  접근 방법

초기에는 queue 자료구조를 이용해 오른쪽에서 왼쪽으로 이동하며 front()에 있는 값보다 작은 경우 queue에 저장, 큰 경우 queue를 비우고 해당 인덱스로 이동하는 구조로 코드를 구현

-> 이 경우 idx 처리 부분에서 문제가 생겨 구현되지 않음

 

* 왼쪽에서 오른쪽으로 stack에 저장하며 레이저를 수신할 탑을 선정하는 알고리즘으로 변경 *

레이저를 수신할 탑보다 높이가 낮은 경우 결과를 저장, 수신할 탑보다 높이가 높은 경우 레이저를 수신할 탑을 갱신

 

  코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> height(N);
    for (int i = 0; i < N; i++) cin >> height[i];

    stack<pair<int, int>> s;
    vector<int> result(N, 0);

    for (int i = 0; i < N; i++) {
        while (!s.empty() && s.top().first <= height[i]) {
            s.pop();
        }

        if (!s.empty()) {
            result[i] = s.top().second + 1;
        }


        s.push({height[i], i});
    }

    for (int i = 0; i < N; i++) cout << result[i] << " ";

    return 0;
}

 

링크

2493번: 탑