문제
총 N개의 문자열로 이루어진 집합 S가 주어진다. M개의 문자열이 주어질 때, 이 문자열들 중 집합 S에 포함된 것이 총 몇 개인지 구하는 문제이다.
입력
첫째 줄에 N과 M(1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N줄에 집합 S에 포함되는 문자열이 주어진다. 다음 M줄에 포함 여부를 확인할 문자열이 주어진다. 각 문자열은 알파벳 소문자로만 이루어져 있으며 길이는 500을 넘지 않는다.
출력
M개의 문자열 중 집합 S에 포함된 문자열의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 11 baekjoononlinejudge baekjoon hello ba ojassembly baekjoon baekjoononline baekjoonon baekjoononlinejudge baek baekjoon online ojassembly as baekjoononline baekjoononlinejudge | 4 |
풀이
HashSet을 이용해 N개의 문자열을 O(1) 조회 가능한 집합으로 구성하고, M개의 문자열 각각에 대해 포함 여부를 확인한다.
- N개의 문자열을
HashSet에 삽입하여 집합 S를 구성한다. - M개의 문자열을 순서대로 읽으면서
set.contains()로 포함 여부를 O(1)에 확인한다. - 포함된 문자열의 개수를 카운트하여 출력한다.
핵심 아이디어: HashSet의 평균 O(1) 조회 특성을 활용하면 O(N + M) 시간에 풀 수 있다. TreeSet을 사용하면 O((N + M) log N)이 되어 다소 느리다. 문자열의 길이가 최대 500이므로 해시 충돌 가능성은 낮다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Day145BOJ14425문자열해쉬맵 {
static int N, M, cnt;
static HashSet<String> set;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
cnt = 0;
set = new HashSet<>();
for (int i = 0; i < N; i++)
set.add(br.readLine());
for (int i = 0; i < M; i++)
if (set.contains(br.readLine()))
cnt++;
System.out.println(cnt);
br.close();
}
}복잡도
- 시간: O(N + M) — HashSet 삽입/조회 평균 O(1)
- 공간: O(N)