Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.

6. 문자열 집합

14425번

트라이보다 쉽게 풀 수 있는 문제지만, 연습을 위해 트라이로 풀어 봅시다.

이번 문제는 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 문제이다.

Java / Python

• Java

트라이를 이용한다. (HashMap을 이용하면 더 빠르고 간단하게 구할 수 있다.)

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

public class Main {
	public static class Node {
		Node[] child = new Node[26];
		boolean is_last;

		public Node() {
		};
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

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

		Node root = new Node();

		while (N-- > 0) {
			String str = br.readLine();
			Node cur = root;
			for (int i = 0; i < str.length(); i++) {
				char cha = str.charAt(i);
				if (cur.child[cha - 'a'] == null)
					cur.child[cha - 'a'] = new Node();
				cur = cur.child[cha - 'a'];

				if (i == str.length() - 1)
					cur.is_last = true;
			}
		}

		int answer = 0;
		while (M-- > 0) {
			String str = br.readLine();
			Node cur = root;
			for (int i = 0; i < str.length(); i++) {
				char cha = str.charAt(i);
				if (cur.child[cha - 'a'] == null)
					break;
				cur = cur.child[cha - 'a'];

				if (i == str.length() - 1 && cur.is_last)
					answer++;
			}
		}

		bw.write(answer + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

python으로 트라이를 이용하면 시간 초과가 나 Pypy3로 돌려야 해, python은 그냥 map을 이용하여 간단히 구해보았다.

import sys

N, M = map(int, sys.stdin.readline().strip().split())
str = sys.stdin.read().split()
S, cmd = set(str[:N]), str[N:]
print(sum(1 for i in cmd if i in S))