백준 2493 탑

https://www.acmicpc.net/problem/2493

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

using namespace std;

vector<pair<int, int>> arr;
vector<int> ans;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    arr.resize(n);
    ans.resize(n, 0);

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        arr[i] = make_pair(temp, i + 1);
    }

    stack<pair<int, int>> st;



    for (int i = 0; i < n; i++) {
        if (!st.empty()) {
            while (!st.empty() && st.top().first < arr[i].first) {
                st.pop();
            }
            if (!st.empty()) {
                ans[i] = st.top().second;
            }

        }
        st.push(arr[i]);
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }


    return 0;
}

1. 문제

높이가 서로 다른 탑의 개수 n과 각 탑의 높이가 주어진다. 모든 탑은 그 옥상에서 왼쪽 수평방향으로 신호를 송신한다. 각 신호는 가장 먼저 만나는 탑 한 개에서만 수신이 가능하다. 이 때, 각 탑의 신호에 대해 수신한 탑의 번호를 출력한다. 단, 어떤 탑도 신호를 받지 못하는 경우에는 0을 출력한다.

2. 풀이

핵심은 왼쪽으로 가면서 송신탑보다 높은 첫 탑이 수신탑이 된다는 것이다. 스택을 사용하여 풀 수 있다.

vector<pair<int, int>> arr;

for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        arr[i] = make_pair(temp, i + 1);
    }

 탑의 번호를 구해야 하므로 탑의 높이와 번호를 pair로 입력받애 배열에 저장한다.

stack<pair<int, int>> st;



    for (int i = 0; i < n; i++) {
        if (!st.empty()) {
            while (!st.empty() && st.top().first < arr[i].first) {
                st.pop();
            }
            if (!st.empty()) {
                ans[i] = st.top().second;
            }

        }
        st.push(arr[i]);
    }

 스택이 비어있지 않다면 연산을 진행하는데, 스택의 top(왼편으로 가면서 연산)을 확인하면서 송신 탑보다 낮은 위치에 있는 건물은 스택에서 pop한다. 현재 건물의 오른편에 있는 건물에서 송신했을 때는 현재 건물에 막히므로 pop된 건물은 연산에 필요가 없으므로, 이렇게 연산하여 현재 건물에서 왼편으로 가면서 건물의 높이를 확인할 수 있다. 

 위 연산이 끝나고 스택에 남아있을 경우 송신 신호가 top에 해당하는 건물에 막혔다는 뜻이므로 해당 건물의 번호를 ans 배열에 추가한다. 이후 현재 건물을 스택에 넣어준다.

 위 연산이 끝나고 결과 배열 ans를 출력하면 정답을 구할 수 있다.