백준 2493번 탑

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

분류는 스택으로 되어있지만 우선순위 큐를 이용하여 푼 문제였습니다.

알고리즘은 아래와 같습니다.

1. 오른쪽에서부터 왼쪽으로 레이저를 발사하기 때문에 오른쪽에서부터 반복문을 시작합니다.

2. 우선 minHeap 형태를 띄는 우선순위 큐를 정의하고 N번째 탑의 높이와 인덱스를 넣습니다.

3. (N - 1)번째 탑부터 현재 우선순위 큐의 top(cur)에 저장되어있는 탑의 높이와 비교합니다.

i) 현재 인덱스에 위치한 탑의 높이가 cur의 높이보다 크거나 같다면 레이저 신호를 수신했으므로 결과 배열 cur번째 탑 인덱스에 현재 인덱스를 저장하고 3번을 반복합니다.

ii) 현재 인덱스에 위치한 탑의 높이가 cur의 높이보다 작다면 우선순위 큐에 들어가있는 다른 탑들 또한 레이저 신호를 못 보내므로 반복문을 탈출합니다.

#include <iostream>

#include <vector>

#include <functional>

#include <queue>

using namespace std;

 

const int MAX = 500000 + 1;

 

int height[MAX];

int result[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int i = 1; i <= N; i++)

                 cin >> height[i];

 

        //minHeap(높이, 인덱스)

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        pq.push({ height[N], N }); //제일 마지막 탑 높이부터 입력

 

        for (int i = N - 1; i >= 1; i--)

        {

                 while (1)

                 {

                         //pq가 비어있을 경우 바로 탈출

                         if (pq.empty())

                                 break;

 

                         pair<int, int> cur = pq.top();

                         bool popped = false;

 

                         if (cur.first <= height[i])

                         {

                                 pq.pop();

                                 result[cur.second] = i;

                                 popped = true;

                         }

 

                         //제일 낮은 탑의 신호도 못 받았다면 더 이상 찾아볼 필요가 없다

                         if (!popped)

                                 break;

                 }

                 pq.push({ height[i], i });

        }

 

        for (int i = 1; i <= N; i++)

                 cout << result[i] << " ";

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~