[백준(BOJ)] 2493번 : 탑 - C++[CPP]

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

2493번: 탑

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 자료 구조
• 스택

 

---

 

⊙ 문제 접근 과정

 

stack pair를 이용하여 index와 value를 동시에 push 해주었다.

가장 위에 있는 값의 value는 st.top().second이고 그것에 대한 index는 st.top().first이다.

 

현재 입력 값이랑 기존에 stack에 저장되어 있는 값이랑 비교 후, 신호 수신 가능( 기존에 있는 값이 더 크다면)이라면 index를 출력한다. 만약 stack이 비어있다면 0을 출력한다.

 

자세한 건 아래 코드를 참고하자. 주석을 줄마다 달아놨다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <stack>

using namespace std;

int N, K;
stack<pair<int, int>> st;
//stack ( { index, value } )

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N; //탑의 수

    for(int i=1;i<=N;i++) {
        cin >> K; //비교할 값

        if(st.empty()) { //비어있다면 push 후 0 출력
            st.push({i,K});
            cout << "0 ";
        }
        else {
            while(!st.empty()) {
                if(st.top().second > K) { //신호 수신 가능 시
                    cout << st.top().first<< " "; //index 출력
                    break;
                } else {
                    st.pop(); // 신호 수신 불가 시 pop
                }
            }
        if(st.empty()) cout << "0 "; //스택이 비면 0 출력

        st.push({i,K}); //스택에 push
        }

    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!