문제

BOJ 17219, 비밀번호 찾기

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 사이트 주소에 해당하는 비밀번호가 주어진다. 사이트 주소에 맞는 비밀번호를 출력하기 위해 해시 자료구조를 사용한다.
• C++에선 unordered_map, Java에선 HashMap을 사용한다.

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
#include <unordered_map>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	unordered_map<string, string> map;
	int n, m;
	cin >> n >> m;
	while (n--) {
		string site, pw;
		cin >> site >> pw;
		map[site] = pw;
	}
	while (m--) {
		string site;
		cin >> site;
		cout << map[site] << '\n';
	}
}

Java

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        HashMap<String, String> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            map.put(st.nextToken(), st.nextToken());
        }
        for (int i = 0; i < m; i++) {
            String key = br.readLine();
            bw.write(map.get(key) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}