백준 2493 탑 c++ [컴공과고씨]

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

2493번: 탑

문제를 먼저 이해하면 탑이 서있을 때 오른쪽 탑부터 왼쪽으로 레이저를 쏴서 자신보다 높이가 같거나 높은쪽에 부딪치면 수신하는 탑이 되고 없다면 0을 출력하는 것이다.

 

내가 생각한 문제 접근 방식을 소개하면 일단 처음 입력 받은 탑들을 스택에 넣어준다. 스택에 넣어주는 이유는 오른쪽 탑부터 레이저를 쏘기 때문이다. 이 때 스택에 저장하는 값은 pair를 이용해서 첫번째는 탑의 높이 두번째는 순서를 저장해준다. 순서를 저장하는 이유는 뒤에서 설명하겠다.

 

그 다음 오른쪽 탑 부터 레이저를 쏠것이다. 만약 그 다음 탑을 확인하면서 높이가 자신보다 높은지 아닌지 확인한다.

만약 자신보다 낮다면 자신을 우선 순위 큐에 넣어준다. 이때 우선 순위 큐는 높이 기준 오름차순으로 정렬된다.

이 때 큐도 첫번째 값은 높이 두번째 값은 인덱스 값이다. 이렇게 해주는 이유는 우선 순위 큐의 top값은 전에 나왔던 탑 중 가장 작은 높이의 값을 가르키게 되고 다음 탑의 높이가 더 높다면 큐에서 pop해주면서 정답 벡터에 저장해주면된다.

이런식으로 stack에 있는 탑을 다 확인해 주고 주의해야할 것은 마지막 우선순위 큐에 남아있는 탑들은 수신을 받지 못한 값들이기 때문에 정답 벡터에 넣어주면된다.

 

여기서 인덱스를 저장한 이유가 나오는데 이렇게 우선순위 큐를 사용하게 되면 탑의 순서가 바뀌게 되는데 이때 정답벡터에 인덱스 값을 저장해두었기 때문에 sort 후 출력해 주면된다.

 

그림으로 설명

 

 

만약 위 설명으로 이해가 안된다면 코드 주석을 보면서 천천히 생각해 보시길 바랍니다!

 

전체 코드

#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
struct cmp{
    bool operator()(pair<int, int> a, pair<int, int> b){
        return a.first > b.first;
    } // 우선 순위 큐 정렬 기준 오름 차순으로 바꾸어줌.
};
int n, t;
stack<pair<int, int>> s; 
 
vector<pair<int, int>> v; 
// first : 인덱스, second : 높이 
// -> 정답 출력할 때 인덱스 기준으로 정렬해야함.
 
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
// first : 높이 , second : 인덱스
// -> 정렬할 때는 높이 기준으로 정렬되어야함
 
int main(){
    cin >> n;
    for (int i = 1; i <= n;i++){
        cin >> t;
        s.push(make_pair(t, i));
    }
    int cnt = 0;
    while(!s.empty()){ // 스택이 비면 모든 탑을 확인한 것
        while(!q.empty() && q.top().first <= s.top().first){
            // 높은 탑을 만나 수신이 가능할 탑이 있을 때
            v.push_back(make_pair(q.top().second, n-cnt));
            q.pop();
        }
        // 다음 탑을 확인하러 감.
        q.push(make_pair(s.top().first, s.top().second));
        s.pop();
        cnt++;
    }
    while(!q.empty()){ 
        // 수신 받아줄 탑이 없는 탑들
        v.push_back(make_pair(q.top().second, 0));
        q.pop();
    }
    sort(v.begin(), v.end());
    // 인덱스 순으로 정렬
 
    for (int i = 0; i < n; i++){
        cout << v[i].second << " ";
    } // 정답 출력
 
    return 0;
}

체감 난이도	걸린 시간	참고	사용 알고리즘
중	50min	x	스택 , 우선 순위 큐 (stack, priority queue)