문제 출처

단계별로 풀어보기 > 집합과 맵 > 문자열 집합
https://www.acmicpc.net/problem/14425

문제 설명

N개의 문자열로 이루어진 집합 S가 주어질 때, M개의 문자열들이 주어진다.
이 때, M개의 문자열 중 집합 S에 포함되어있는 갯수를 구하라.

접근 방법

HashMap을 이용하여 N개의 문자열을 저장한다.
이 후, M개의 문자열을 하나씩 받으면서 HashMap의 containsKey 메서드를 이용하여 포함되어있는 경우, result의 갯수를 1 증가시킨다.

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

public class 문자열_집합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        HashMap<String,Integer> hm = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int result = 0;

        for(int i = 0; i < N; i++){
            String s = br.readLine();
            hm.put(s,i);
        }

        for(int i = 0; i < M; i++){
            String t = br.readLine();
            if(hm.containsKey(t)) result++;
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

containsKey 메서드는 O(1)의 시간복잡도를 가진다.
처음 문제를 봤을 때는, String의 startsWith 메서드를 사용하려고 했으나, 이는 시간복잡도를 O(글자의 길이) 만큼 가지기 때문에, HashMap을 이용하므로, 굳이 startsWith을 사용하지 않고, containsKey를 이용하자는 생각이 들었다.

그렇게 해당 풀이는 시간복잡도를 O(N) or O(M)을 가진다.

문제푼 흔적