백준 2493번 탑 (C++)

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

2493번: 탑

문제 요약

 

1.  N개의 탑의 높이가 1열로 주어집니다.

2. 각각의 탑은 자신의 왼쪽에 위치한 탑 중 자신보다 높은 탑에게 신호를 전달할 수 있습니다.

3. 각각의 탑이 신호를 전달할 수 있는 탑의 위치를 출력하세요. 신호를 전달할 수 있는 탑이 존재하지 않을 경우 0을 출력하세요.

 

핵심 포인트

 

N의 값이 최대 500,000이 주어지므로, 무턱대로 2중 for문을 사용했다가 시간초과가 발생할 수 있습니다.

이 문제는 stack을 통해 간단하게 해결할 수 있습니다.

 

문제 풀이

 

1. 변수 n을 선언하고 값을 입력받습니다.

    int n = 0;
    cin >> n;
    stack<pair<int,int>> st; // stack
    vector<int> tower(n+1); // 탑의 높이를 저장할 벡터
    vector<int> ans(n+1); // 각 탑의 정답을 저장할 벡터

이때 편의상 0번째가 아닌 1번째부터 탑의 위치를 저장하기 위해, n+1로 각 벡터의 크기를 지정합니다.

 

2. 탑의 높이를 입력 받으며 동시에 해당 탑에 왼쪽에 위치하면서, 해당 탑 보다 높은 탑의 위치를 출력합니다.

for(int i=1; i<=n; i++) {
        cin >> tower[i]; // 1
        while(!st.empty()){ // 2
            if(st.top().first<tower[i]) st.pop(); // 3
            else break; // 4
        }
        if(st.empty()){ // 5
            ans[i] = 0;
        }
        else ans[i] = st.top().second; // 6
        st.push({tower[i],i}); // 7
    }

(1) 현재 탑의 높이를 입력받습니다.

(2) 스택이 빌때까지 while문을 진행합니다.

(3) 현재 저장된 스택의 top의 '높이' (st.top().first)값이 현재 탑의 높이보다 작을 경우, pop을 합니다.

이 말은 즉슨, 자신보다 왼쪽에 위치한 탑(이하 'A'라 지칭)이 자신의 높이(이하 'B'라 지칭)보다 작다는 뜻이므로, 해당 값은 스택에서 제거해주면 됩니다. 이렇게 제거한 값은 for문이 계속 진행되더라도 영향을 주지 않습니다.

예를들어 tower[1] = A, tower[2] = B, tower[3]=C라고 가정했을때, A보다 B가 크기 때문에 A가 스택에서 제거되어도, C보다 왼쪽에 있으면서 C보다 큰 값은 B이기 때문에 A를 스택에서 제거한 사실이 영향을 주지 않습니다.

(4)  현재 저장된 스택의 top의 '높이' (st.top().first)값이 현재 탑의 높이보다 클 경우, 현재 탑보다 높은 탑을 발견했다는 뜻이므로 while문을 종료합니다.

(5) 만약 st이 비어있다면 자신보다 큰 높이의 탑을 발견하지 못했다는 뜻이므로 ans[i] = 0으로 저장합니다.

(6) 그렇지 않을 경우, st.top().second를 ans[i]로 저장하면 됩니다.

(7) 현재 입력받은 탑의 높이와 그 순서를 스택에 저장합니다.

 

3. 1번부터 n번까지 정답을 출력합니다.

for(int i=1; i<=n; i++) cout << ans[i] << " ";
cout << "\n";

 

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0;
    cin >> n;
    stack<pair<int,int>> st;
    vector<int> tower(n+1);
    vector<int> ans(n+1);
    for(int i=1; i<=n; i++) {
        cin >> tower[i];
        while(!st.empty()){
            if(st.top().first<tower[i]) st.pop();
            else break;
        }
        if(st.empty()){
            ans[i] = 0;
        }
        else ans[i] = st.top().second;
        st.push({tower[i],i});
    }
    for(int i=1; i<=n; i++) cout << ans[i] << " ";
    cout << "\n";
    return 0;
}