[ 백준 ] 9322 / 철벽 보안 알고리즘

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
61/228
post-thumbnail

# Appreciation

/*
 * Problem :: 9322 / 철벽 보안 알고리즘
 *
 * Kind :: Data Structure
 *
 * Insight
 * - 문제만 읽어서는 도통 무슨소리인지...
 *   + 3
 *     SECURITY THROUGH OBSCURITY
 *     OBSCURITY THROUGH SECURITY
 *     TOMORROW ATTACK WE
 *     # 제 1 공개키=PK1
 *       제 2 공개키=PK2 라 하면,
 *       아! 규칙(PK1-> PK2) 를 보고
 *       규칙(평문 -> 암호문) 인 평문을 구하라는 것이다
 *       -> 여기서 규칙은
 *          PK1 인덱스 : 1 2 3
 *          PK2 인덱스 : 3 2 1
 *          로, PK1의 단어가 PK2 로 재배치되는 방식을 뜻한다
 *
 * - map<int,string> i2w / PK2 의 인덱스 -> PK2 에서 단어
 *   map<string,int> w2i / PK2 의 단어 -> PK1 에서 인덱스
 *   + PK2 의 인덱스 i 가 주어지면
 *     PK2[i] = PK2 에서 단어
 *     w2i[i2w[i]] = 평문에서 인덱스
 *     즉, 평문 에서 PK2[i] PK2[i] 는 w2i[i2w[i]] 인덱스를 가진다
 *
 * Point
 * - i2w = O(1), w2i = O(1)
 *   + 만약 Map 이 아니라 다른 자료구조를 썼다면
 *     find 로 단어에 해당하는 인덱스를 매번 찾아야 하니
 *     O(N) 의 시간복잡도를 지녀 비효율적인 코드가 되었을 것이다
 */

# Code

//
//  Codeforces
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <map>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        int N; cin >> N;
        string PK1[N], PK2[N], C[N];
        for (int i=0; i<N; i++)
            cin >> PK1[i];
        for (int i=0; i<N; i++)
            cin >> PK2[i];
        for (int i=0; i<N; i++)
            cin >> C[i];

        // Process
        map<int,string> i2w; /* PK2 의 인덱스 -> PK2 에서 단어 */
        for (int i=0; i<N; i++) {
            i2w[i] = PK2[i];
        }
        map<string,int> w2i; /* PK2 의 단어 -> PK1 에서 인덱스 */
        for (int i=0; i<N; i++) {
            w2i[PK1[i]] = i;
        }

        string D[N]; /* 평문 */
        for (int i=0; i<N; i++) {
            D[w2i[i2w[i]]] = C[i];
        }

        // Control : Output
        for (int i=0; i<N; i++) {
            cout << D[i] << ' ';
        } cout << endl;

    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글