[백준] 2493 탑 C++

1. 문제 설명

• 문제 바로가기

---

2. 풀이 과정

• 문제 해결의 흐름 

    1. 탑의 높이가 하나씩 추가되는 형태군!! 추가될 때마다 출력할지 한 번에 결과를 출력할지 생각해봐야겠다. 

    2. 음.. 탑의 높이가 추가될 때마다 바로 직전에 추가된 탑의 높이와 비교하는게 어떨까? 만약 추가된 탑의 높이가 더 크다면 바로 직전 탑이 수신을 절대 받지 못할 것이고, 이전에 추가된 탑의 높이가 더 크다면 수신을 받을 수 있겠군!!! 

    3. 이를 다음과 같이 구체화하여 조건문으로 나타내면 쉽게 풀 수 있을듯! 아래 조건문에 맞지 않는 높이는 수신을 받을 수 없기 때문에 삭제 처리해면 될듯 

if (새로 추가되는 높이 < 이전에 추가된 높이) {
	cout << 이전에 추가된 높이의 추가된 순서 인덱스 << " ";
}

    4.  후입선출의 자료에 관심이 크기에 stack을 사용하여 풀어보자!!

 

• 코드 

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;
    stack<pair<int, int> > S;
    for (int i = 0; i < N; ++i) {
        int curHeight;
        cin >> curHeight;

        while(!S.empty()) {
            if (curHeight < S.top().first) {
                cout << S.top().second << " ";
                S.push(make_pair(curHeight, i+1));
                break;
            }
            S.pop();
        }

        if (S.empty()) {
            cout << "0 ";
            S.push(make_pair(curHeight, i+1));
        }

    }


    return 0;
}

---

3. 후기 

 후입선출의 단서를 최대한 빠르게 찾아 stack을 이용해 풀면 되는 문제였다. 단, pair을 모른다면 인덱스값을 저장하는 방법에서 고생할 거 같은 문제!!