[백준/JAVA] 14426_접두사 찾기

백준🔗

14426번: 접두사 찾기

 

문제

 

 

 

간단 풀이

오늘 들은 알고리즘 특강에서 '트라이' 자료구조에 대해 배웠다.

그래서 트라이를 연습해볼 수 있는 문제를 풀어봤다.

 

우선, 트라이는 문자열 집합을 관리하는 트리이다. 정점마다 알파벳이 하나씩 대응되어 들어있고, 접두사와 접미사 관련한 문제에서 많이 사용되는 자료구조라고 한다.

단어가 많을수록 앞이 겹치는 단어들이 많아지기 때문에 이를 효율적으로 탐색할 수 있게 하기 위한 자료구조인데 메모리는 더 사용하지만 탐색의 효율이 좋아지는 자료구조라고 생각하면 될 것 같다.

정점 클래스에는 대응되는 알파벳(char), 자식 정점들(hashmap) 외에도 해당 정점이 끝인 문자열이 존재하는지(boolean), 하위의 문자열 개수(int) 등 문제 풀이에 필요한 속성들을 추가해서 활용할 수 있다.

 

 

예제에서 주어진 5개의 단어(baekjoononlinejudge, startlink, codeplus, sundaycoding, codingsh)를 트라이 구조로 만들면 아래와 같이 완성된다.

 

 

트라이 구조를 완성해두고 이후에 들어오는 문자열들이 이 중 적어도 하나의 접두사인지 판별하려면 알파벳을 하나씩 따져보면 된다.

예를 들어 "baekjoon"이라는 단어가 접두사에 해당하는지 보려면

루트의 자식 노드 중에 b가 있는지 확인하고, b가 있다면 해당 정점으로 이동한다.

다음으로는 b의 자식 노드 중에 a가 있는지 확인하고, a가 있다면 해당 정점으로 이동한다.

이 과정을 반복하면서 n까지 찾았다면 접두사에 해당하는 것이다.

반면 "online"이라는 단어는

루트의 자식 노드 중에 o가 없기 때문에 접두사에 해당하지 않는다고 판단할 수 있다.

 

코드

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

public class Main {
	static class Trie {
		char alphabet;
		Map<Character, Trie> children = new HashMap<>();

		// 알파벳 주어졌을 때 생성자
		public Trie(char alphabet) {
			this.alphabet = alphabet;
		}

		// 기본 생성자
		public Trie() {

		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 집합 S에 포함되어 있는 문자열 개수
		int M = Integer.parseInt(st.nextToken()); // 검사해야하는 문자열 개수
		Trie head = new Trie(); // 루트 노드
		// N개의 단어 입력받아서 트라이 구조로 만들기
		for (int i = 0; i < N; i++) {
			String word = br.readLine();
			Trie idxTrie = head;
			for (int j = 0; j < word.length(); j++) {
				char alphabet = word.charAt(j);
				// 새로운 정점인 경우 하위에 추가해주기
				if (!idxTrie.children.containsKey(alphabet)) {
					idxTrie.children.put(alphabet, new Trie(alphabet));
				}
				// 해당 알파벳 정점으로 이동하기
				idxTrie = idxTrie.children.get(alphabet);
			}
		}
		// M개의 문자열에 대해 각각이 접두사에 해당하는지 판단하기
		int cnt = 0;
		for (int i = 0; i < M; i++) {
			String word = br.readLine();
			Trie idxTrie = head;
			for (int j = 0; j < word.length(); j++) {
				char alphabet = word.charAt(j);
				// 접두사에 해당하지 않으면 탐색 종료
				if (!idxTrie.children.containsKey(alphabet))
					break;
				idxTrie = idxTrie.children.get(alphabet);
				if (j == word.length() - 1)
					cnt++;
			}
		}
		System.out.println(cnt);
	}
}

 

참고 자료