백준 13211 자바 - Passport Checking (BOJ 13211 JAVA)

문제 : boj13211

 

 

  hashset의 개념을 안다면 바로 풀 수 있다. 혹시 모를 경우 brute force로는 O(NM) 이므로 풀 수 없다. 그러니 정렬 후 이분탐색 O(NlogN + MlogN)으로 풀면 된다. 하지만 정렬 후 이분탐색을 아는 사람이 hashset의 개념을 모를리 없으므로 사실상 해시로 풀면 되는 문제이다. 이 경우 O(N+M) 이 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        HashSet<String> hs = new HashSet<>();
        while(n-->0) hs.add(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int cnt = 0;
        while(m-->0) if (hs.contains(br.readLine())) cnt++;
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}