백준[20551] Sort 마스터 배지훈의 후계자

문제 풀이

문제 링크

http://icpc.me/2051

풀이

map을 사용해서 풀었다.

그냥 모든 쿼리에 대해 탐색을 하면 O(NM)이기 때문에 시간 초과가 발생한다.  그렇기 때문에 탐색하는 시간을 줄여야 한다.

이때 idx[쿼리] = 쿼리의 인덱스로 미리 다 저장해놓으면 탐색을 하지 않고 빠르게 인덱스를 구할 수 있다. 그러나 쿼리의 범위가 -10^9 ~ 10^9으로 매우 크기 때문에 배열을 선언할 수 없다. 그래서 map을 이용하여 값들을 모두 저장해놓으면 쿼리당 O(logN)에 처리할 수 있다. 

다른 풀이로는 탐색을 할 때 이분 탐색을 이용하여 인덱스를 빠르게 구할 수도 있다. lower_bound를 이용하여 idx를 구하고 그 인덱스에 있는 값이 주어진 쿼리와 같은 수인지 체크하면 된다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int NN = 1e5 + 5;

vector<int> arr;
map<int, int> idx;

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        int ipt; scanf("%d", &ipt);
        arr.push_back(ipt);
    }
    sort(arr.begin(), arr.end());
    for (int i = 0; i < n; i++) {
        if (!idx.count(arr[i])) idx[arr[i]] = i;
    }
    while (m--) {
        int query; scanf("%d", &query);
        printf("%d\n", idx.count(query) ? idx[query] : -1);
    }
}