https://www.acmicpc.net/problem/17219
시간 5초, 메모리 256MB

input :

• N M(1 ≤ N, M ≤ 100,000)
• 사이트 주소 비밀번호(사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 구성, 비밀번호는 알파벳 대문자. 모두 길이는 최대 20)

output :

• 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력

조건 :

• 메모장에서 비밀번호를 찾아주는 프로그램

---

c++의 hashmap, 혹은 map을 사용해보기 위한 문제.
파이썬의 딕셔너리 처럼 hashing을 사용한 자료구조에 저장한 후 검색을 수행해 빠르게 답을 얻을 수 있다.

다음 풀이

1. 비밀번호를 저장
2. 사이트 주소 입력시 출력

빠른 검색이 필요하니 딕셔너리를 사용한다는 것만 알면 된다.

import sys

n, m = map(int, sys.stdin.readline().split())
data = dict()

for _ in range(n):
    a, b = sys.stdin.readline().split()
    data[a] = b

for _ in range(m):
    print(data[sys.stdin.readline().rstrip()])

fastio

출처 : ios_base::sync_with_stdio(false); cin.tie(null); 구문을 추가해주는 이유

ios_base::sync_with_stdio(false); 
cin.tie(null);

해당 구문을 통해 c의 stdio와 cpp의 iostream의 동기화가 끊어져 속도를 더 빠르게 한다.
동기화 시에는 동일한 버퍼를 사용해 딜레이가 발생한다고 한다.

"알고리즘을 풀 때는 보통 싱글 쓰레드 환경이기 때문에 결과에 영향이 없고 버퍼를 분리하기 때문에 속도가 빨라집니다."

map

이진 트리의 구조를 가지는 아주 좋은 자료구조이다.
탐색할 때 hash보다는 느리지만 그래도 나쁘지 않은 성능, 적은 입력을 가져 이 문제를 통과할 수 있따.

unordered_map

해시 테이블을 사용한 딕셔너리와 비슷한 자료구조이다.
O(1)의 속도를 자랑해 매우 빠르다.

둘 다 중복된 키를 가지지 않는다.

#include "iostream"
#include "map"
#include "string"
#include "unordered_map"

using std::ios;
using std::cout; using std::cin;
using std::string; using std::unordered_map;

int n, m;
unordered_map<string, string> data;

void init(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

}

int main(){
    init();
    cin >> n >> m;

    for (int i = 0; i < n; ++i){
        string a, b;
        cin >> a >> b;
        data.insert(make_pair(a, b));
    }

    for (int i = 0; i < m; ++i){
        string temp;
        cin >> temp;
        cout << data[temp] << "\n";
    }
    return 0;
}