[C/C++] BOJ 2493 :: 탑

BOJ 2493 :: 탑

문제 링크 : https://www.acmicpc.net/problem/2493

나의 풀이

머릿속으로 생각해서 풀었는데 바로 맞춰서 놀랐다.. 나의 스마트함에 감..탄.. ㅈㅅ

* 탑은 왼쪽의 자신보다 높은 탑으로부터 영향을 받는다.

하나씩 탐색하면서 stack에 push한다.

ex) 6 9 5 7 4 에서

6은 0

stack : 6

9는 6보다 크므로 stack을 뒤져 이전에 탐색했던 탑의 높이와 비교한다.

이 때, stack에 있던 값을 빼내며 탐색한다. => 다시 넣을 필요가 없다. 

ex) 7 6 5 4 3 2 6 일 때, 가장 끝 6은 두 번째 6을 만날 때까지 stack에서 pop한다.

그 후, ans를 갱신하고 두 번째 6을 pop하면 stack에는 7만 남게되고

다시 자신의 값 6을 push하면 최종적으로 stack에는 첫번째 7과 마지막 6만 남는다.

7 6 사이에 있던 6 5 4 3 2 는 다음 탑의 높이가 어떻든 전혀 영향을 주지 않는 data이다.

stack에 충족하는 값이 없다. 9는 0

stack : 6 => stack : 9

5는 9보다 작으므로 9의 idx이다. => 2

stack : 9 => stack : 9 5

7은 5보다 크므로 stack을 뒤져 이전에 탐색했던 탑의 높이와 비교한다. => 2

stack : 9 5 에서 9를 만날 때까지 pop한 후, 자신의 값을 push

=> stack : 9 7

4는 7보다 작으므로 7의 idx이다. => 4

stack : 9 7 => stack : 9 7 4

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_2493/BOJ_2493.cpp

// 백준알고리즘 2493번 :: 탑
#include <iostream>
#include <stack>
using namespace std;
 
int N;
int ans[500001];
// idx, height
stack<pair<int, int>> st;
 
int main()
{
    int height = 0;
    cin >> N;
    cin >> height;
    st.push(make_pair(1, height));
 
    for (int i = 1; i < N; i++)
    {
        cin >> height;
 
        // height가 st.top보다 크면
        // stack에서 큰 값을 찾는다.
        if (height > st.top().second)
        {
            while (!st.empty() && st.top().second < height)
            {
                st.pop();
            }
            // stack에 height보다 큰 값이 없으면
            if (st.empty())
            {
                ans[i] = 0;
            }
            // stack에 heigth보다 큰 값이 있으면
            else
            {
                ans[i] = st.top().first;
                if (st.top().second == height) st.pop();
            }
        }
        // height가 st.top보다 작거나 같으면 ans[i] = st.top().first다.
        else
        {
            ans[i] = st.top().first;
        }
        st.push(make_pair(i+1, height));
    }
 
    for (int i = 0; i < N; i++)
    {
        cout << ans[i] << ' ';
    }
 
    return 0;
}