๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] Q.5052 ์ ํ๋ฒํธ ๋ชฉ๋ก ๋ฌธ์ ํ์ด - java
๐ ๋ฌธ์
https://www.acmicpc.net/problem/5052
์ ํ๋ฒํธ ๋ชฉ๋ก์ด ์ฃผ์ด์ง๋ค. ์ด๋, ์ด ๋ชฉ๋ก์ด ์ผ๊ด์ฑ์ด ์๋์ง ์๋์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ํ๋ฒํธ ๋ชฉ๋ก์ด ์ผ๊ด์ฑ์ ์ ์งํ๋ ค๋ฉด, ํ ๋ฒํธ๊ฐ ๋ค๋ฅธ ๋ฒํธ์ ์ ๋์ด์ธ ๊ฒฝ์ฐ๊ฐ ์์ด์ผ ํ๋ค.
์๋ฅผ ๋ค์ด, ์ ํ๋ฒํธ ๋ชฉ๋ก์ด ์๋์ ๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด๋ณด์
- ๊ธด๊ธ์ ํ: 911
- ์๊ทผ: 97 625 999
- ์ ์: 91 12 54 26
์ด ๊ฒฝ์ฐ์ ์ ์์ด์๊ฒ ์ ํ๋ฅผ ๊ฑธ ์ ์๋ ๋ฐฉ๋ฒ์ด ์๋ค. ์ ํ๊ธฐ๋ฅผ ๋ค๊ณ ์ ์์ด ๋ฒํธ์ ์ฒ์ ์ธ ์๋ฆฌ๋ฅผ ๋๋ฅด๋ ์๊ฐ ๋ฐ๋ก ๊ธด๊ธ์ ํ๊ฐ ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์ด๋ค.
๋ฐ๋ผ์, ์ด ๋ชฉ๋ก์ ์ผ๊ด์ฑ์ด ์๋ ๋ชฉ๋ก์ด๋ค.
๐ ์ ๊ทผ๋ฒ
Q.5052 ์ ํ๋ฒํธ ๋ชฉ๋ก ๋ฌธ์ ์ ๋๋ค.
์ฃผ์ด์ง ๋ฌธ์ ์ ์์๋ฅผ ๋ณด๋ฉด ํ ๋ฒํธ๊ฐ ๋ค๋ฅธ ๋ฒํธ์ ์ ๋์ด์ธ ๊ฒฝ์ฐ๊ฐ ์์ด์ผํฉ๋๋ค.
Trie๋ฅผ ์ด์ฉํ์ฌ ํ์ด๊ฐ ๊ฐ๋ฅํฉ๋๋ค.
Trie๋ฅผ ์ด์ฉํ์ฌ ์ ํ๋ฒํธ ๋ชฉ๋ก๋ค์ ์ ๋ ฅํ๋๋ฐ
์ ํ๋ฒํธ ์ ๋ ฅ ๋ฐ๋ ๋์ค์ ์ด๋ฏธ ์์ฑ ๋ ์ ํ๋ฒํธ๊ฐ ์๋ค๋ฉด
ex) 911 ์ด ์ด๋ฏธ ์
๋ ฅ ๋์ด์๊ณ
์ ์์ด์ ์ ํ๋ฒํธ๊ฐ ์
๋ ฅ์ด ๋ ๋
911 -25426 ์ด๋ฏธ 911์์ ๊ธด๊ธ์ ํ 911์ ๋ฒํธ๊ฐ ์์ฑ๋๋ฒ๋ฆผ
ํ ๋ฒํธ๊ฐ ๋ค๋ฅธ ๋ฒํธ์ ์ ๋์ด์ธ ๊ฒฝ์ฐ์ด๋ฏ๋ก ์ผ๊ด์ฑ์ด ์๋ ๋ชฉ๋ก์์ ์ ์ ์์ต๋๋ค.
์ด๋ฅผ ์ด์ฉํด ๋ฌธ์ ํ์ด๊ฐ ๊ฐ๋ฅํฉ๋๋ค.
๐ป ์ฝ๋
package problem.string.trie;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Main_5052 {
static int t,n;
static Trie trie;
static StringBuilder sb = new StringBuilder();
static String[] phoneNumbers;
public static void main(String[] args) throws IOException {
input();
System.out.println(sb.toString());
}
public static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
for(int i=0; i<t; i++) {
trie = new Trie();
n = Integer.parseInt(br.readLine());
phoneNumbers = new String[n];
for(int j=0; j<n; j++){
phoneNumbers[j] = br.readLine();
}
solve();
}
br.close();
}
public static void solve() {
Arrays.sort(phoneNumbers);
for(int i=0; i<n; i++){
if (trie.insert(phoneNumbers[i]) == false) {
sb.append("NO\n");
return;
}
}
sb.append("YES\n");
}
static class TrieNode {
public Map<Character, TrieNode> childNodes = new HashMap<>();
private boolean isLastChar;
public Map<Character, TrieNode> getChildNodes() {
return this.childNodes;
}
public boolean isLastChar() {
return this.isLastChar;
}
public void setLastChar(boolean lastChar) {
this.isLastChar = lastChar;
}
}
static class Trie {
private TrieNode rootNode;
public Trie() {
rootNode = new TrieNode();
}
// ์์ ๋
ธ๋ ์ถ๊ฐ
boolean insert(String word) {
TrieNode thisNode = this.rootNode;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if(thisNode.childNodes.get(currentChar) == null){
thisNode.childNodes.put(currentChar,new TrieNode());
}
thisNode = thisNode.childNodes.get(currentChar);
if(thisNode.isLastChar == true)
return false;
}
thisNode.setLastChar(true);
return true;
}
}
}