문제 링크 : https://www.acmicpc.net/problem/5052
처음 전화번호 목록 문제를 접했을 때 이중 포문을 이용하여 시간 초과가 발생했다.
어떤 방법이 있을까 하고 고민할 때 스터디원이 Trie 자료구조를 사용하면 풀 수 있다고 힌트를 주었다.
하지만 Trie 자료구조를 모르고 있었기에 학습하여 문제를 해결하였고 Trie 자료구조를 이용하지 않더라도 풀 수 있는 방법이 있길래 Trie 자료구조를 사용하지 않는 방법으로 문제를 풀어보았다.
아래와 같이 소스를 공유한다.
Trie 자료구조를 이용한 구현
public class 전화번호목록 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int e = 0; e < T; e++) {
int ca = Integer.parseInt(br.readLine());
List<String> list = new ArrayList<>();
Trie t = new Trie();
for (int i = 0; i < ca; i++) {
String word = br.readLine();
list.add(word);
t.insert(word);
}
boolean is = false;
for(String k : list) {
if(t.contains(k)) {
is = true;
break;
}
}
sb.append((is == true) ? "NO":"YES").append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
}
public class Trie {
private TrieNode rootNode;
public Trie() {
this.rootNode = new TrieNode();
}
public void insert(String word) {
TrieNode root = this.rootNode;
for (int i = 0; i < word.length(); i++) {
root = root.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
}
root.setIsLastChar(true);
}
public boolean contains(String word) {
TrieNode temp = this.rootNode;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = temp.getChildNodes().get(ch);
if(node == null) return false;
temp = node;
}
if(temp.isLastChar()) {
if(temp.getChildNodes().isEmpty()) {
return false;
}
}
return true;
}
public void delete(String word) {
delete(this.rootNode, word, 0);
}
public void delete(TrieNode node, String word, int idx) {
char ch = word.charAt(idx);
if(!node.getChildNodes().containsKey(ch)) throw new Error(word + " : 존재하지 않습니다.");
TrieNode child = node.getChildNodes().get(ch);
idx++;
if(idx == word.length()) {
if(!child.isLastChar()) throw new Error(word + " : 존재하지 않습니다.");
child.setIsLastChar(false);
if(child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
}else {
delete(child, word, idx);
if(!child.isLastChar() && child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
}
}
public boolean isRootEmpty() {
return this.rootNode.getChildNodes().isEmpty();
}
}
public class TrieNode {
private Map<Character, TrieNode> childNodes = new HashMap<>();
private boolean isLastChar;
Map<Character, TrieNode> getChildNodes() {
return this.childNodes;
}
boolean isLastChar() {
return this.isLastChar;
}
void setIsLastChar(boolean is) {
this.isLastChar = is;
}
}Trie 자료구조는 트리 형식으로 문자열을 찾는 자료구조이다.
Trie 자료구조를 이용하지 않은 구현
public class 전화번호목록 {
public static Comparator<String> compare = new Comparator<>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int e = 0; e < T; e++) {
int c = Integer.parseInt(br.readLine());
List<String> list = new ArrayList<>();
for (int i = 0; i < c; i++) {
list.add(br.readLine());
}
Collections.sort(list, compare);
boolean is = false;
for (int i = 1; i < c; i++) {
if(list.get(i).startsWith(list.get(i-1))) {
is = true;
break;
}
}
System.out.println((is == true) ? "NO":"YES");
}
}
}주어지는 문자들을 정렬하고 startsWith 함수를 이용하여 비교한다.
문제를 푸는 방식이 다양하여 한 가지 문제를 풀더라도 여러 방법으로 풀어 다양한 접근 방식을 습득하려고 노력중이다.
참고 자료
- Trie 자료 구조 : the-dev.tistory.com/3
[자료구조] Trie(트라이)-2 : 자바로 구현하기
안녕하세요. 개발개입니다. 지난 시간 기초 개념에 이어, Trie를 자바로 구현하는 과정을 알아보겠습니다. 구현 과정에서 람다를 사용하기 때문에 Java8 베이스로 진행합니다. [KR/자료구조] - [자료
the-dev.tistory.com
[백준/5052번] 전화번호 목록(NCPC 2007)[Java]
문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없
blue-boy.tistory.com
'알고리즘 > 문제풀이 - 백준온라인저지' 카테고리의 다른 글
| [BOJ] 배열 돌리기 1 16926.JAVA (0) | 2021.04.12 |
|---|---|
| [BOJ] 달팽이 1913.JAVA (0) | 2021.04.11 |
| [BOJ] 토마토 7569.JAVA (0) | 2021.04.06 |
| [BOJ] 소년점프 16469.JAVA (0) | 2021.03.29 |
| [이것이 코딩테스트다] 게임 개발 (JAVA) (0) | 2021.03.18 |