[백준 2493번] 탑

---

문제 화면

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

문제 풀이

이 문제는 stack의 자료구조를 응용하는 문제이다. 6198번 옥상정원꾸미기와 거의 비슷한 문제이다. 문제의 핵심은 왼쪽 건물보다 더 큰건물이 나오는 순간 왼쪽 건물은 필요 없기 때문에 과감하게 pop해주는데 오른쪽 건물보다 더 큰 왼쪽 건물이 나올 때 까지 pop해준다. 그러다 empty 상태가 되면 오른쪽 건물의 레이저를 수신할 건물이 없다는 의미이기 때문에 ‘0’을 출력해준다. 반대로 왼쪽 건물이 오른쪽 건물보다 더 크다면 왼쪽 건물이 레이저를 수신할 수 있기 때문에 왼쪽 건물의 인덱스를 출력해준다. 그리고 오른쪽 건물(현재 인덱스)을 기록해둔다.

6198번 옥상정원꾸미기와 마찬가지로 O(n)의 시간복잡도로 해결이 가능하고 가장 최근의(top) 건물을 사용하고 필요 없어지면 지워도(pop) 된다는 부분에서 스택 자료구조가 적합한 문제라고 볼 수 있다.

제출 코드(stack 사용)

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

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    vector<int> v;
    stack<int> s;
    stack<int> idx;

    int a, temp;
    cin >> a;

    for(int i = 0 ; i < a ; i++) {
        cin>>temp;
        v.push_back(temp);
    }

    for(int i = 0 ; i < v.size() ; i++) {
        while(!s.empty() && s.top()<v[i]) {
            s.pop();
            idx.pop();
        }

        if(s.empty()) cout << "0" << " ";

        else cout << idx.top() << " ";

        s.push(v[i]);
        idx.push(i+1);
    }


    return 0;
}

결론

이 문제는 스택을 얼마나 알고리즘에 응용해서 문제를 풀 수 있는지를 물어보는 문제이다. 알고리즘은 어렵지는 않은데 스택을 사용하여 생각해내기가 쉽지 않고 그래서 골드 티어로 지정된게 아닌가 싶다. 스택을 잘 사용한다는 것(스택 뿐만이 아니라 모든 자료구조가 마찬가지 인 것 같다)은 단순히 문법을 잘 안다는 것이 아닌 어떻게 알고리즘에 녹여서 활용할 수 있는지를 의미하는 것 같다.