[BOJ알고리즘, C++]#2493_탑, 스택, 히스토그램 유형

 

#1. 문제

2493번: 탑

 

---

 

#2. 풀이

 

1. 스택

[자료 구조]#0_선형 자료구조

 

스택은 후입 선출 방식으로 동작하는 선형 자료구조로, 지정된 형식의 데이터를 한쪽 방향으로만 삽입하며, 제거 작업은 반대편 한쪽에서만 가능합니다.

 

2. 히스토그램 유형 문제는 스택으로 풀자!

 

1. 각 송신탑의 높이 값을 차례대로 vector 컨테이너에 저장합니다. 그리고, 빈 스택 하나를 선언합니다.
2. 높이 값을 저장한 vector 컨테이너를 차례대로 순회합니다. 이때, 스택의 top에 위치한 인덱스에 해당하는 높이 값과 현재 위치의 높이 값을 비교하고, 현재 높이 값이 크다면 현재 스택의 top 값을 pop 해줍니다. 이 과정은 stack이 동나거나, top에 위치한 인덱스에 해당되는 높이 값이 현재 위치의 값보다 클 때까지 반복됩니다.
3. 마지막으로, stack이 비어있을 경우 현재 위치의 송신탑이 레이저를 발사하면 왼쪽에 위치한 어느 송신탑도 그 레이저를 받을 수 없습니다. 반면, stack이 비어있지 않을 경우, stack의 top에 위치한 인덱스에 해당되는 높이 값이 현재 송신탑의 레이저를 수신 받게됩니다!

 

---

#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

int N;
vector<int> v, ans;
stack<int> s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    v.resize(N + 1);
    ans.resize(N+1);
    
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i];
    }

    for (int i = 1; i <= N; ++i)
    {
        while (!s.empty() && v[i] > v[s.top()])
        {
            s.pop();
        }

        if (s.empty())
            ans[i] = 0;
        else
            ans[i] = s.top();

        s.push(i);
    }

    for (int i = 1; i <= N; ++i)
        cout << ans[i] << ' ';

    return 0;
}

 

---