백준 탑 2493

문제

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

풀이설명

1. 처음에는 n^2 풀이가 생각이 났다 -> 당연히 안된다 50만이니

2. 투포인터, 스택, 등등 생각해보다가 우큐의 힌트를 받아서 돌진했다.

3. 현재 어떤 위치에 값을 보고있는데 아직 배정되지 않은 번호들이 있을 경우 현재 값이 배정되지않은 값보다 크면 배정을 해준다

   if (!pq.empty() &&arr[i] > pq.top().first) {
            while (!pq.empty() && arr[i] > -pq.top().first) {
                //cout << arr[i] << " " << -pq.top().first << " " << pq.top().second << endl;
                ans[pq.top().second] = i;
                pq.pop();
            }
            pq.push({ -arr[i], i });
        }

   위에서 자꾸 실수한점은 우큐는 맥스힙으로 되니 따로 정렬하기 싫어서 -로 넣었는데 , 이때 꺼낼때는 -를 붙어서 나와야하는데 그것을 인식하지 않아서 자꾸 틀리게 되었다.

4. while로 돌려야한다 왜냐? 배정되지않고 남아 있는 것들을 현재 위치로 레이저를 발사할 수 있다면 다 발사 해야하기때문에.

소스

#include <bits/stdc++.h>

using namespace std;

int arr[600000];
int ans[600000];
int n;
priority_queue < pair<int, int>, vector<pair<int, int>>> pq;   // 값, 해당 위치 번호 인덱스 (1- base) 
int main() {

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> arr[i];

    for (int i = n; i >= 1; i--) {

        if (!pq.empty() &&arr[i] > pq.top().first) {
            while (!pq.empty() && arr[i] > -pq.top().first) {
                //cout << arr[i] << " " << -pq.top().first << " " << pq.top().second << endl;
                ans[pq.top().second] = i;
                pq.pop();
            }
            pq.push({ -arr[i], i });
        }
        else {
            pq.push({ -arr[i],i });
        }

    }

    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}