[Lv.2] 문자열 집합

문제 이해하기

집합 S: 총 N개의 문자열로 이루어진 문자열 집합.
검사 문자열: 총 M개의 문자열로 이루어진 검사해야 하는 문자열 집합.
집합 S에 포함된 문자열 중 검사 문자열에 포함된 문자열이 몇 개나 있는지를 구해야 합니다.

알고리즘 설계

1. 집합 S에 포함된 문자열을 저장하기 위해 HashSet을 활용합니다.
2. 집합 S에 속하는 문자열을 입력받고 HashSet에 저장합니다.
3. 검사 문자열을 입력받으면서 HashSet에 해당 문자열이 포함되어 있는지 확인합니다.
4. 포함되어 있다면 카운트를 증가시킵니다.
5. 최종적으로 카운트된 값을 출력합니다.

소스코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 집합 S에 속하는 문자열을 저장할 Set 자료구조를 생성합니다.
        Set<String> stringSet = new HashSet<>();

        // 문자열의 개수 N과 검사해야 하는 문자열의 개수 M을 입력받습니다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 집합 S에 포함되어 있는 문자열을 입력받고, Set에 저장합니다.
        for (int i = 0; i < N; i++) {
            stringSet.add(br.readLine());
        }

        // 집합 S에 포함되어 있는 문자열 중에서 입력으로 주어진 문자열들이 몇 개나 포함되는지를 카운트합니다.
        int count = 0;
        for (int i = 0; i < M; i++) {
            String testString = br.readLine();
            if (stringSet.contains(testString)) {
                count++;
            }
        }

        // 결과를 출력합니다.
        System.out.println(count);
    }
}

테스트 케이스 예시

**입력:**
5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
codeplus
codeminus
startlink
starlink
sundaycoding
codingsh
codinghs
sondaycoding
startrink
icerink

출력:

4

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 문자열의 개수를 N, 검사해야 하는 문자열의 개수를 M이라고 할 때 O(N + M)입니다.