[백준 2493] 탑 (C++)

문제

백준 2493

2493번: 탑

풀이

먼저 탑의 높이와 인덱스를 받는 stack을 선언합니다.

탑의 높이를 입력해주고, 뒤에서 부터 다음 과정을 실행합니다.

1. 스택이 비었을 경우에는 탑의 높이와 인덱스를 스택에 push 합니다.

2. 스택이 비어있지 않을 때는, 스택의 top과 현재 탑의 높이를 비교하여, top이 작다면 레이저가 도달한 것이므로

레이저가 닿는 탑의 위치를 저장하는 배열 receive에 탑의 위치를 저장해준 후, stack을 pop 합니다.

3. 계속해서 top이 작다면 이 작업을 반복합니다.

4. top이 현재 탑의 높이보다 크다면 push 합니다.

소스 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include<iostream> #include<stack> #include<vector> using namespace std;   int tower[500001]; int receive[500001]; int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     int n;     cin >> n;     for (int i = 1; i <= n; i++)     {         cin >> tower[i];     }     //높이, 인덱스     stack<pair<int, int>> st;     int idx = n;     for (int i = n; i > 0; i--)     {         if (!st.empty())         {             while (st.top().first < tower[i])             {                receive[st.top().second] = i;                 st.pop();                 if (st.empty())                     break;             }         }         st.push(make_pair(tower[i], i));     }     for (int i = 1; i <= n; i++)     {         cout << receive[i] << ' ';     }     return 0; } Colored by Color Scripter

cs