Baekjoon 9322번 철벽 보안 알고리즘

문제

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

걸린 시간

00 : 50 : 30

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
typedef long long ll;
using namespace std;

int n;
vector<pair<string, int>> key1;
vector<string> key2, crypto, decrypto;

void binsearch(int after){
    int mid;
    int left = 0;
    int right = n-1;
    while(left <= right){
        mid = (left+right)/2;
        if(key2[after] == key1[mid].first)
            break;
        else if(key2[after] < key1[mid].first)
            right = mid - 1;
        else
            left = mid + 1;
    }
    int before = key1[mid].second;
    decrypto[before] = crypto[after];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n;
        key1.resize(n); key2.resize(n);
        crypto.resize(n); decrypto.resize(n);
        string key;
        for(int i = 0; i < n; i++){
            cin >> key;
            key1[i].first = key;
            key1[i].second = i;
        }
        for(auto& i : key2) cin >> i;
        for(auto& i : crypto) cin >> i;
        sort(key1.begin(), key1.end());
        for(int i = 0; i < n; i++)
            binsearch(i);
        for(int i = 0; i < n; i++)
            cout << decrypto[i] << " ";
        cout << "\n";
    }
    return 0;
}

2중 for문으로 공개키 1, 2를 일일이 모두 비교해 어떻게 재배치되었는지 확인하는 방법은 O(n²t) 로 비교 연산만 1억번이기 때문에 시간초과가 난다. 탐색의 시간을 줄이기 위해 이분 탐색을 사용했고 비교 연산이 nlogn 으로 줄어들어 제한시간 1초안에 통과할 수 있었다.