[백준] 14427번 수열과 쿼리 15 (C++)

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

 

 

이 문제는 N개의 수열이 존재할때 각 쿼리에 맞는 수행을 하는 문제이다.

 

이 문제에서 2개의 쿼리가 주어진다.

 

1. 인덱스, 요소가 주어지며 인덱스에 대한 값을 요소로 바꾸는 쿼리이다.

2. 현재 수열에서 가장 작은 값의 인덱스를 출력한다. 이때 가장 작은 값이 여러개인 경우 인덱스가 가장 작은 것을 출력한다.

 

이때 수열의 크기는 최대 10만이며 쿼리의 개수도 10만이다 이를 단순하게 완전탐색으로 진행하게 된다면

이는 O(NM)으로 10억이 넘어가며 시간초과가 난다.

 

따라서 시간을 단축할 수 있는 방법을 찾아야 하는데 이때 최소힙이 생각이 났다.

 

나의 방법은 이러한데

초기에 배열을 입력받고 최소힙에 (배열 값, 인덱스)를 넣는다.

 

1번쿼리가 입력된 경우 배열의 값을 변경하고 (변경된 값, 인덱스)를 넣는다.

 

이후 2번 쿼리가 입력된 경우 루트에 있는 값을 꺼내고 그 값의 인덱스를 확인하여 변경된 값과 수열의 인덱스 값과 비교를 한다.

만약 다를 경우 이는 힙에 저장된 값이 이전의 값이므로 꺼내는것을 반복한다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M;
int arr[100001];
priority_queue<pii, vector<pii>, greater<pii>> pq;

void solve() {
    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a;

        if(a == 1) {
            cin >> b >> c;

            arr[b] = c;
            pq.push({c, b});
        }
        else {
            int value = pq.top().first;
            int idx = pq.top().second;

            if(arr[idx] != value) {
                while(arr[idx] != value) {
                    pq.pop();
                    value = pq.top().first;
                    idx = pq.top().second;
                }
            }

            cout << idx << endl;
        }
    }
}

void input() {
    cin >> N;

    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
        pq.push({arr[i], i});
    }

    cin >> M;

    solve();
}

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

    input();
}