[S4] 9322. 철벽 보안 알고리즘

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

9322번: 철벽 보안 알고리즘

문제를 보고 당황한 문제. 문제 이해도 솔직히 잘 안됐고, 처음 접근 방법은 어찌저찌 잘 했지만, 한 가지 놓친 부분이 있었다. 그 부분에 대해 알아보자.

문제 이해부터 해보자.

 

제 1 공개키 -> 제 2 공개키로 가는데 패턴이 있다. 

제 1 공개키에서 주어진 단어들에 순서가 있지 않은가? 그 순서가 제 2 공개키에서 뒤바뀌게 된다. 하지만 이 패턴이 평문 -> 암호키에도 똑같이 적용이 되는 것이다.(근데 왜 문제에서는 규칙의 반대로 재배치하여 만들어진다 했지? 이거때문에 개짜증)

어쨋든. 근데 출력을 보면 평문을 전부 출력하는 것이다. 그러니까 단어를 출력해야 한다. 이 단어는 암호문에서 주어지는 단어이다. 그렇기 때문에 우리는 저장해야 할 요소가 2가지가 된다. 

1. 출력할 단어를 저장할 배열

2. 제 1공개키 -> 제 2공개키 패턴

그런데, 여기에서 제 1공개키 -> 제 2공개키의 패턴을 파악하기 위해서는 제 1공개키로 부터 받는 단어를 저장하고, 제 2공개키에서 받은 단어로 부터 find함수를 통해 몇번째에 존재하는지 알아야 한다. 그렇기 때문에 총 3가지를 저장해야 할 요소가 필요하게 된다.

 

자. 이제 무엇을 저장해야 하는지에 대한 이해는 끝났다. 이제는 어떻게가 남았다.

우리는 패턴을 생각해야 한다. 패턴을 어떤식으로 저장해야 할까?

제 2공개키를 입력받을 때, 순서대로 입력을 받는다. 이것을 int형 배열에 제 1공개키에서 해당 단어가 몇번째로 나왔는지 저장하는 것이다. 

 

자 그럼 제 1공개키에서 입력받은 단어가 몇번째로 나왔는지 어떻게 가져와야 할까?

제 1공개키를 입력받을 때, 몇번째로 입력받았는지와 함께 저장하는 것이다. 그리고, 자료구조에서 find함수를 사용하여 단어를 찾고, 그 단어와 함께 저장된 수를 가져오는 것이다.

 

여기에서 어떤 자료구조를 사용해야 좋을까?

우리는 삽입과 검색을 많이 이용하게 될 것이다. 

삽입은 제 1공개키를 몇번째에 입력되었는지와 단어를 함께 저장해야 할 때 사용되고,

검색은 제 2공개키를 입력받을 때, 해당 단어가 몇번째에 입력되었는지를 알아야 하기 때문이다.

그러므로 검색과 삽입의 비용이 적은 자료구조 unordered_map(hashmap)이 된다.

그러면 우리는 제 1공개키를 입력받을 때, unordered_map(hashmap)에 저장을 해준다.

혹시 모르니 unordered_map을 잘 모르겠다면 다음 글을 참고하라.

https://jhcard.tistory.com/83

 

다음으로 int형 배열에 제 2공개키가 입력될 때 find함수로 입력된 단어가 몇번째에 저장되었는지 가져오고 그 값을 int형 배열에 저장하는 것이다. 이것이 패턴을 알기 위한 방법이다.

 

이제 마지막이다. 암호문을 입력받는다. 

처음에 우리는 출력할 단어들의 문자열을 배열 형식으로 사용한다고 하였다. 그리고, 그 배열에 저장될 형식으로 출력이 될 것이다. 그렇기 때문에, 우리는 저장할 때 출력할 순서에 맞게 저장을 해야 한다.

어떻게 순서에 맞게 저장을 할까?

위에서 우리는 패턴을 알게 되었다. x번째로 입력된 단어는 y번째로 가게끔 [x] = y형태로 저장이 되었는데, 우리는 이 패턴을 이용하여 해당 자리에 입력된 단어를 저장하는 것이다. 이 과정을 반복하게 되면 정답이 나오게 된다. 

 

다음은 내가 작성한 코드이다.

#include <cstdio>
#include <iostream>
#include <unordered_map>

int main(void) {
    std::cin.tie(0); std::cout.tie(0);
    std::ios_base::sync_with_stdio(false);
    
    int T, n; std::cin >> T;
    std::unordered_map<std::string, int> m;
    std::string c[1000];
    int key[1000];

    std::string tmp;
    while (T--) {
        std::cin >> n;
        for (int i = 0; i < n; i++) std::cin >> tmp, m.insert({tmp, i});
        for (int i = 0; i < n; i++) std::cin >> tmp, key[i] = m[tmp]; 
        for (int i = 0; i < n; i++) std::cin >> tmp, c[key[i]] = tmp; 
        for (int i = 0; i < n; i++) std::cout << c[i] << ' '; 
        std::cout << '\n';
        m.clear();
    }
}

하지만, 이 코드를 더 단순화 할 수 있다. 나는 unordered_map이 익숙하지 않아 insert문, find함수 등을 사용하였는데, 그냥 파이썬에서 사용하는 사전과 비슷하게 사용할 수 있더라. 그러니까 2번째 for문을 보면 key[i] = m[tmp]로 unordered_map에 string, int형으로 저장되어 있는 형태를 [string]에 int형이 저장되어 있다는 형태로 쉽게 접근이 된다는 것이다.

m.insert({tmp, i})도 m[tmp] = i로 변경이 가능하다.

 

그리고, 나는 처음에 unordered_map을 사용하지 않고 그냥 map을 사용하였다. 그래서 이 문제에 대한 블로그를 작성하고 있다.