문제 설명

문자열 집합 S가 주어지고,
여러 개의 문자열이 입력될 때

집합 S에 포함된 문자열 개수

를 구하는 문제이다.

---

입력

첫째 줄

N M

• N : 집합 S의 크기
• M : 검사할 문자열 개수

다음 N줄

집합 S의 문자열

다음 M줄

검사할 문자열

조건

1 ≤ N, M ≤ 10000
문자열 길이 ≤ 500

---

출력

집합 S에 포함된 문자열 개수 출력

---

입력 예시

5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
...

출력 예시

4

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

문자열 존재 여부를 빠르게 판단

---

가능한 방법

1. 이중 반복 → O(N×M) → 비효율
2. 정렬 + 이분탐색
3. HashSet

---

내가 작성한 코드

나는 HashSet을 사용해서 빠르게 해결했다.

코드

import java.util.*;

class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        Set<String> S = new HashSet<>();
        int result = 0;

        for(int i = 0; i < N; i++) {
            S.add(sc.next());
        }

        for(int i = 0; i < M; i++) {
            if(S.contains(sc.next()))
                result++;
        }

        System.out.print(result);
    }
}

---

강의 코드 (이분 탐색)

배열을 정렬한 뒤 이분 탐색으로 확인하는 방식이다.

코드

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static boolean isExist(String[] arr, String x) {

        int l = 0, r = arr.length - 1;

        while (l <= r) {

            int m = (l + r) / 2;
            int compareResult = arr[m].compareTo(x);

            if (compareResult < 0) l = m + 1;
            else if (compareResult > 0) r = m - 1;
            else return true;
        }

        return false;
    }

    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        String[] arr = new String[N];

        for (int i = 0; i < N; i++)
            arr[i] = sc.next();

        Arrays.sort(arr);

        int count = 0;

        while (M-- > 0) {
            String x = sc.next();
            if (isExist(arr, x))
                count++;
        }

        System.out.println(count);
    }
}

---

강의 코드 (Set 방식)

코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        Set<String> set = new HashSet<>();

        for (int i = 0; i < N; i++)
            set.add(sc.next());

        int count = 0;

        while (M-- > 0) {
            String x = sc.next();
            if (set.contains(x))
                count++;
        }

        System.out.println(count);
    }
}

---

내 코드 vs 강의 코드 비교

1. 접근 방식

내 코드

HashSet 사용

→ 빠른 존재 여부 확인

---

강의 코드

방식	특징
이분 탐색	정렬 후 탐색
Set	HashSet 사용

---

2. 핵심 차이

방식	특징
내 코드	자료구조 기반 해결
강의 코드	알고리즘 + 자료구조

---

3. 시간복잡도

내 코드 (HashSet)

O(N + M)

---

강의 코드 (이분 탐색)

O(N log N + M log N)

---

4. 언제 어떤 걸 쓰는가

상황	추천
존재 여부만 필요	HashSet
정렬 + 탐색 필요	이분 탐색

---

5. 문자열 비교 방식

이분 탐색에서는

compareTo()

사용

→ 사전순 비교

---

핵심 개념

1. Set

중복 제거 + 빠른 탐색

---

2. 이분 탐색

정렬된 상태에서 탐색

---

3. 문자열 비교

str1.compareTo(str2)

---

시간 복잡도

방식	복잡도
내 코드	O(N + M)
강의 코드	O(N log N)

---

정리

이 문제는 단순한 문자열 문제지만
핵심은

빠른 탐색 방법 선택

이다.

내 코드는 HashSet을 사용해
가장 효율적으로 해결했다.

강의 코드에서는

• 이분 탐색
• Set

두 가지 방법을 비교했다.

핵심 차이는 다음과 같다.

내 코드   → 자료구조 활용 (HashSet)
강의 코드 → 알고리즘 활용 (Binary Search)

즉, 이 문제는

탐색 문제 → Set or Binary Search

패턴을 익히기 좋은 문제이다.