[백준] S3 14425번 문자열 집합 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

14425번: 문자열 집합

[문제] 

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

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

[입력]

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

[출력]

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

 

 

---

[풀이]

1. 해쉬 셋을 사용하여 n개의 문자열들을 입력받는다.

2. contains()를 사용해 m개의 문자열들이 포함되어있는지 확인 후 있다면 카운트를 증가시켜준다.

[접근]

1. 배열에 문자열들을 담아 compareTo를 이용해 비교한다. (이 경우, 시간 초과)

2. 해쉬셋을 사용해 빠른 검색을 해야 한다.

[코드]

아래의 코드처럼 배열에 받아서 배열로 처리를 하려고 하니 시간 초과가 발생했다.

그래서 생각한 것이 빠른 탐색을 할 수 있는 해쉬 셋을 사용하는 것이었다.

package BOJ_silver;

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

public class Main_S3_14425_fail {
	static int n;
	static int m;
	static String[] s;
	static int count;

	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());
		
		s = new String[n];
		
		for (int i = 0; i < n; i++) {
			s[i] = br.readLine();
		}
		
		for (int i = 0; i < m; i++) {
			String str = br.readLine();
			
			for (int j = 0; j < n; j++) {
				if (s[j].compareTo(str) == 0)
					count++;
			}
		}
		
		System.out.println(count);
	}
}

해쉬셋을 사용한 코드

package BOJ_silver;

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

public class Main_S3_14425 {
	static int n;
	static int m;
	static HashSet<String> set;
	static int count;

	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());
		
		set = new HashSet<>();
		
		for (int i = 0; i < n; i++) {
			set.add(br.readLine());
		}
		
		for (int i = 0; i < m; i++) {
			String str = br.readLine();
			
			if (set.contains(str))
				count++;
		}
		
		System.out.println(count);
	}
}

[실수]

시간 초과를 생각하지 않고 배열로 처리를 하려고 했던 것이 큰 실수였다. 이를 해결하기 위해 빠른 검색을 할 수 있는 해쉬 셋을 사용하였다.