[Java] BOJ 5052번 전화번호 목록

[Java] BOJ 5052번 전화번호 목록

풀이

Trie를 사용해서 해결했습니다.

자바를 사용한 Trie 코드를 잘 설명한 블로그가 있어 링크를 공유하겠습니다.

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; public class Main { public static int t, n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(""); t = Integer.parseInt(br.readLine()); for (int tc = 0; tc < t; ++tc) { PriorityQueue pq = new PriorityQueue<>(new Comparator() { public int compare(String o1, String o2) { return Integer.compare(o1.length(), o2.length()); } }); Trie trie = new Trie(); n = Integer.parseInt(br.readLine()); boolean flag = true; for (int i = 0; i < n; ++i) { pq.offer(br.readLine()); } trie.insert(pq.poll()); while (!pq.isEmpty()) { String cur = pq.poll(); if (trie.contains(cur)) { flag = false; break; } trie.insert(cur); } if (flag) { sb.append("YES

"); } else { sb.append("NO

"); } } System.out.println(sb); } public static class TrieNode { // 자식 노드를 저장할 맵 private Map childNodes = new HashMap<>(); // 마지막 글자인지 private boolean isLast; // 자식 노드맵을 리턴 Map getChildNodes() { return this.childNodes; } // 마지막 원소 getter boolean getLast() { return this.isLast; } // 마지막 원소 setter void setLast(boolean isLast) { this.isLast = isLast; } } public static class Trie { // 루트 노드 private TrieNode rootNode; Trie() { rootNode = new TrieNode(); } void insert(String word) { TrieNode thisNode = this.rootNode; for (int i = 0; i < word.length(); ++i) { // map의 computeIfAbsent 메소드는 // 만약 자식노드에서 word.charAt(i)에 해당하는 위치에 노드가 생성이 되어있다면 그 값을 가져오고 // 없다면 새로 객체를 만들어준다. thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode()); } // 해당 단어의 마지막 위치를 true로 변경 // computeIfAbsent의 결과로 word의 마지막 문자 // 위치가 for문을 통해 thisNode에 들어가있다 thisNode.setLast(true); } boolean contains(String word) { TrieNode thisNode = this.rootNode; for (int i = 0; i < word.length(); ++i) { // 만약 마지막 글자라면 // 즉, 현재 단어보다 숫자는 적지만 // 현재 단어와 같은 문자로 이루어진 단어라면 멈추게한다. if (thisNode.getLast()) { break; } char ch = word.charAt(i); // 현재 글자에 해당하는 자식노드들을 얻어온다. TrieNode node = thisNode.getChildNodes().get(ch); if (node == null) { return false; } thisNode = node; } // 만약 현재 단어의 마지막 글자에 isLast값이 true라면 // 해당 문자는 노드에 포함된 값이 된다. return thisNode.getLast(); } // 사용자가 편하게 사용하게 하기 위함 void delete(String word) { delete(this.rootNode, word, 0); } private void delete(TrieNode thisNode, String word, int index) { char ch = word.charAt(index); // 만약 단어를 탐색하다 단어에 포함된 문자가 없다면 // 해당 단어는 노드에 포함되지 않은 단어가 되므로 if (!thisNode.getChildNodes().containsKey(ch)) { throw new Error("There is no [" + word + "] in this Trie."); } TrieNode childNode = thisNode.getChildNodes().get(ch); index++; // 현재 위치가 맨 마지막 글자라면 if (index == word.length()) { // 만약 단어를 탐색하다 단어에 포함된 문자가 없다면 // 해당 단어는 노드에 포함되지 않은 단어가 되므로 if (!childNode.getLast()) { throw new Error("There is no [" + word + "] in this Trie."); } // 마지막 단어임을 해제하여 해당 단어가 포함되지 않도록 만든다. childNode.setLast(false); // 마지막 단어에 해당하는 노드에 자식노드 전체가 존재하지 않는다면 // 해당 단어보다 길면서 현재 인덱스까지 같은 문자를 가진 단어가 없다는 의미가 되므로 // 현재 노드에서 지워버린다. if (childNode.getChildNodes().isEmpty()) { thisNode.getChildNodes().remove(ch); } } else { // 다음 글자를 지운다. delete(childNode, word, index); // 맨 마지막 문자가 아닌데 자식 노드 전체가 비어있다면 // 즉, 재귀함수를 통해 맨 마지막 문자가 이미 삭제된 단어라면 // 현재노드에서 지워준다. if (!childNode.getLast() && childNode.getChildNodes().isEmpty()) { thisNode.getChildNodes().remove(ch); } } } } }

from http://comgong-man.tistory.com/223 by ccl(A) rewrite - 2021-08-23 20:00:54