[Gold IV] 전화번호 목록 - 5052
성능 요약
메모리: 185984 KB, 시간: 800 ms
분류
자료 구조(data_structures), 정렬(sorting), 문자열(string), 트리(trees), 트라이(trie)
문제 설명
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
- 긴급전화: 911
- 상근: 97 625 999
- 선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
풀이
트라이 문제라는데, 그냥 트리로 구현해서 풀었다.
사용한 로직은 트라이 알고리즘과 비슷한 것 같다
숫자를 한글자씩 root에서 시작해서 자식으로 매달아 추가한다.
이미 현재 노드의 자식으로 해당 숫자가 존재한다면 해당 숫자가 리프노드인지를 판단한다.
리프 노드라면 일관성 있는 목록이 아니기 때문에 NO를 반환한다.
처음에는 입력 순서대로만 구현해서 틀렸는데, 이후에 길이순으로 정렬한 후 입력값을 검증하였다.
package BOJ.Gold.g4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_5052_전화번호목록 {
static class Node {
int curr;
Map<Integer, Node> child;
public Node(int curr) {
this.curr = curr;
this.child = new HashMap<>();
}
public boolean addNode(int newNode) {
if (this.child.containsKey(newNode))
return false; // 이미 있음
this.child.put(newNode, new Node(newNode)); // 자식 노드 매달기
return true; // 추가 완료
}
}
static int N;
public static void main(String[] args) throws IOException {
// 번호를 트리로 매달기 -> 트리로 매달다가 이미 트리에 있는 노드인데 리프 노드라면 일관성 X
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
out:
while (T-- > 0) {
N = Integer.parseInt(br.readLine());
Node root = new Node(0); // root 노드 설정
String[] input = new String[N];
for (int i = 0; i < N; i++)
input[i] = br.readLine();
Arrays.sort(input, Comparator.comparingInt(String::length));
for (int i = 0; i < N; i++) {
Node curr = root; // 현재 노드 확인
String number = input[i];
for (int j = 0; j < number.length(); j++) {
int num = number.charAt(j) - '0';
if (curr.addNode(num)) {
// 새로 추가함
curr = curr.child.get(num); // 현재 노드 변경
} else {
// 이미 있다
curr = curr.child.get(num); // 자식 노드로 이동
// 이미 있는 노드라면 리프 노드인지 판단하기
if (curr.child.size() == 0) {
sb.append("NO").append("\n");
continue out;
}
}
}
}
// 모두 추가했다면
sb.append("YES").append("\n");
}
System.out.print(sb);
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 17182 - 우주 탐사선 (자바 Java) (0) | 2023.01.13 |
---|---|
[백준] 15591 - MooTube (Silver) (자바 Java) (0) | 2023.01.11 |
[백준] 2533 - 사회망 서비스(SNS) (자바 Java) (0) | 2023.01.07 |
[백준] 9328 - 열쇠 (자바 Java) (0) | 2023.01.02 |
[백준] 2166 - 다각형의 면적 (자바 Java) (0) | 2023.01.02 |