(Java) 백준 14425번 - 문자열 집합

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

문제

> 총 N개의 문자열로 이루어진 집합 S가 주어진다.

> 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

접근

N개의 문자열을 입력받아 집합 S를 만들어놓고 M개의 문자열을 입력받아 이 M개의 문자열이 S안에 있나 확인하기 위해선
최악의 경우 10,000 x 10,000번의 연산을 한다. 추가로 문자열의 길이가 최대 500이라고 했으므로 100,000,000번에 500을 또 곱한 횟수의 연산이 이루어진다.
따라서 집합 S를 맵에 저장한 뒤, M을 입력받으며 맵에 해당 문자열인 key값이 있는지 확인하고 있다면 수를 누적한다.

문제해결

> N과 M을 입력받고, N개의 문자열을 저장할 집합을 Map으로 선언한다.
> N개의 문자열을 입력받고 맵에 해당 문자열을 key값으로 value는 1로 저장한다.
> M개의 문자열을 입력받으며 constrainskey함수로 입력받은 문자열이 있는지 확인한다.
> 있다면 cnt를 누적하고 출력한다.

코드

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    //14425번 문자열 집합
    static BufferedReader br;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        Map<String, Integer> m = new HashMap<>();

        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            m.put(str, 1);
        }
        int cnt = 0;
        for(int i = 0; i < M; i++) {
            String str = br.readLine();
            if(m.containsKey(str)) cnt++;
        }
        System.out.print(cnt);
    }
}

후기

예전에 듣보잡이란 문제를 풀 때, NxM번해서 푼적이 있었다. 그 때 map을 사용하는걸 알게 됐고 이를 적용해서 풀었다.
map에 저장해놓으면 constrainskey를 쓸때, NxM이 아니라 Mx최대 글자수500 한거 만큼만 탐색을 하게 된다.