[BOJ] 백준 14425번 문자열 집합 (Java)

#14425 문자열 집합

난이도 : 실버 3

유형 : 문자열/ 트라이

14425번: 문자열 집합

▸ 문제

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

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

▸ 입력

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

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

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

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

▸ 출력

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

 

문제 풀이  

그냥 자료구조 Map을 통해 간단하게 풀 수 있는 문제이다.  또한 문자열 탐색 트리인 트라이(Trie) 자료구조의 기본 형태로 이에 대한 연습 문제로도 풀이를 할 수 있다.

 

설계

트라이(Trie) 자료구조를 구현하여 N개의 문자열을 저장해준다. 그 다음 입력되는 M개의 문자열을 트라이(Trie)에 저장된 문자열과 비교하여 마지막 terminal노드까지 true이면 완전히 일치하는 것이므로 (카운트+1)을 해준다.

 

트라이 내부구조는 문자를 차례대로 저장해주는 Map자료구조인 childNode와 해당 노드가 마지막인지 알려주는 terminal이 존재한다.

class TrieNode{
	Map<Character, TrieNode> childNode = new HashMap<>();
	boolean terminal;
}

 

트라이에 새로운 문자열 추가하는 insert 메소드와 어떤 문자열(str)이 트라이에 존재하는 문자열인지 확인해주는 contains 메소드를 추가적으로 구현해줘야 한다.

public void insert(String word) {
	TrieNode trieNode = this;
	for(int i=0; i<word.length(); i++) {
		char c = word.charAt(i);

		// tmp childNode에 c없으면 추가 
		trieNode.childNode.putIfAbsent(c, new TrieNode());
		trieNode = trieNode.childNode.get(c);

		// 마지막 문자 terminal 
		if(i== word.length()-1) {
			trieNode.terminal = true;
			return;
		}
	}
}

public boolean contains(String word) { 
	TrieNode trieNode = this;
	for(int i=0; i<word.length(); i++) {
		char c= word.charAt(i);
		TrieNode node = trieNode.childNode.get(c);

		if(node == null) {
			return false; // 다음 문자가 없으면 false 
		}
		trieNode = node;
	}

	// 해당 단어로 종료하는 문자가 있는 경우 false
	return trieNode.terminal; 
}

 

 

예시로 {"code", "coding"}을 입력받았다면 트라이(Trie)에는 다음과 같이 저장된다. 파란색을 칠한 노드는 문자열의 끝을 나타내는 노드로 terminal = true이다. 만약 여기서 "cod"를 대입한다면 d는 terminal이 false이므로 포함되지 않는 문자열이라고 판단할 수 있다. 반대로 "code"를 입력받으면 e는 terminal노드이므로 포함되는 문자열이라고 확인할 수 있는 것이다.

 

트라이노드 예시

 

구현

1. 트라이 자료구조에 N개의 문자열을 차례대로 입력한다. tNode.insert(in);
2. M개의 문자열을 트라이에 저장된 문자열과 비교하면서 terminal노드가 일치하면 카운트+1를 해준다. if(tNode.contains(str)) cnt++;

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	static class TrieNode{
		Map<Character, TrieNode> childNode = new HashMap<>();
		boolean terminal;
		
		TrieNode(){
			/* no-op */ 
		}
		
		public void insert(String word) {
			TrieNode trieNode = this;
			for(int i=0; i<word.length(); i++) {
				char c = word.charAt(i);
				
				// tmp childNode에 c없으면 추가 
				trieNode.childNode.putIfAbsent(c, new TrieNode());
				trieNode = trieNode.childNode.get(c);
				
				// 마지막 문자 terminal 
				if(i== word.length()-1) {
					trieNode.terminal = true;
					return;
				}
			}
		}
		
		public boolean contains(String word) { 
			TrieNode trieNode = this;
			for(int i=0; i<word.length(); i++) {
				char c= word.charAt(i);
				TrieNode node = trieNode.childNode.get(c);
				
				if(node == null) {
					return false; // 다음 문자가 없으면 false 
				}
				trieNode = node;
			}
			// 해당 단어로 종료하는 문자가 있는 경우 false
			return trieNode.terminal; 
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		TrieNode tNode = new TrieNode();
		for(int i=0; i<n; i++) {
			String in = br.readLine();
			tNode.insert(in);
		}
		
		int cnt=0;
		for(int i=0; i<m; i++) {
			String str = br.readLine();
			if(tNode.contains(str)) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}