[백준] (5052) 전화번호 목록
링크 : https://www.acmicpc.net/problem/5052
사용 언어 : JAVA
내 생각
초기 생각
트라이 구조를 활용하자.
트라이(trie) 자료구조란?
동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조이다. 주로 문자열이 키인 경우가 많다.
쉽게 말해 그냥 문자열을 트리 구조로 표현(할 때 주로 사용)하는 것인데, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다는 특징이 있다. 루트는 빈 문자열에 연관된다.
이 자료구조를 어떻게 활용할 수 있을까?
하나의 Node 객체에 담겨야하는 데이터는 두가지라고 생각했다.
- boolean: 이 노드를 마지막으로 갖는 문자열이 있는가?
- Node[10]: 자식 노드 (자식으로 올 수 있는게 0~9, 총 10가지이므로 그냥 크기 10짜리 배열을 생각했다)
Node[10]으로 만드니까 확실히 메모리 리소스를 많이 사용해야 했다.
나는 노드마다 데이터(문자)를 저장하고 그 문자가 있는지 일일이 찾아야하는게 귀찮아서 아예 배열의 인덱스로 찾아가도록 만든건데
음.. Node 배열 말고 List나 Set을 사용하면 더 나으려나 모르겠다ㅎ
트라이의 루트를 Node root로 두고 N가지 전화번호를 모두 삽입을 하는데, 삽입을 하는 과정에서 일관성에 어긋나면 바로 "NO"를 출력하고 아무 일 없이 모두 삽입이 완료되면 "YES"를 출력한다.
삽입과정
각 문자열의 0번째~n-1번째 문자열을 루트에서부터 내려오며 차례로 삽입하는데, 부모와 겹치지 않는 문자만을 삽입한다.
첫번째 전화번호가 123, 두번째 전화번호가 124일 때를 예로 들자.
맨 처음 root의 자식 배열 child[]은 다 null 일 것이다. 첫번째 전화번호에서 0번째 문자(1)을 삽입하는데, root의 child[1]=null이다. 이 경우 child[1]에 new Node를 할당해서 그 노드에서 다시 다음 문자를 삽입할 수 있는지 탐색한다.
첫번째 전화번호를 다 삽입하고 두번째 전화번호를 삽입할 때는 어떻게 될까.
cur = root일 때, cur.child[ second[0]==1 ] 존재
cur = cur.child[ second[0] ], cur.child[ second[1]==2 ] 존재
cur = cur.child[ second[1] ], cur.child[ second[2]==4 ] 존재 X => cur.child[4]에 새로운 노드를 할당해준다. 또 이번이 마지막 노드이므로 방금 할당한 새 노드에 마지막 표기를 해준다.
최종적으로 저런 모습이 되게끔 만들었다.
그리고 문자열을 삽입하는 과정에서 일관성을 해치지 않는지 확인해줘야 했다.
이 문제의 경우 조건이 어떤 문자열 A를 접두사로 가지는 문자열 B가 있으면 일관성 X 인데, 이는
- root에서부터 차례로 내려오며 노드를 탐색할 때, 현재 탐색 중인 노드를 마지막으로 갖는 문자열이 있으면 일관성 X
- 현재 부모 노드에 삽입해야하는 노드가 문자열의 마지막 노드일 때, 이미 누가 그 자리에 Node 객체를 할당해 놓은 경우 일관성 X
정도로 나타낼 수 있다. (문자열을 길이 순으로 정렬해 둔다면 1번만 확인하면 된다.)
여하튼 저 두가지에서 걸린다면 바로 "NO" 출력 후 다음 테스트 케이스로 넘어간다.
최종 코드
import java.util.*;
public class Main_BJ_5052_전화번호_목록 {
static int N;
static Node root;
// 트라이 자료구조 사용
// 노드마다 1)이 노드를 끝으로 하는 문자열 유무, 2) 10개 노드 자식 을 가짐
// 전화번호 하나씩 트라이에 추가할 때 마다 root에서부터 타고 내려가서
// 방문하는 노드가 마지막인 문자열 있는지 확인,
// 내가 마지막 노드인데 이미 누가 왔던 노드인지 확인 하면서 새로운 노드 추가해 감
// 중간에 에러 안나면 정상적으로 insert 된 것
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
ArrayList<String> address;
String yes = "YES", no = "NO", ret;
for(int t=0; t<T; t++){
N = Integer.parseInt(br.readLine());
address = new ArrayList<>();
// br.readLine()으로 하나씩 로직 돌릴거면서
// 중간에 return으로 멋대로 끊지 말아야 한다
// 아니면 처음부터 입력값 다 받고난 뒤에 돌려야 한다 멍청인가봐
for(int i=0; i<N; i++) {
address.add(br.readLine());
}
root = new Node();
ret = yes;
for (String a: address){
if(!insert(a.toCharArray())){
ret = no;
break;
}
}
sb.append(ret+"\n");
}
System.out.println(sb);
}
private static boolean insert(char[] address) {
Node cur = root;
int num;
for(int a=0, n=address.length; a<n; a++){
num = address[a] - '0';
if(cur.isEnd) return false;
if(cur.child[num]==null) cur.child[num] = new Node();
else if(a==n-1) return false;
cur = cur.child[num];
}
cur.isEnd = true;
return true;
}
static class Node{
boolean isEnd;
Node[] child;
public Node(){
isEnd = false;
child = new Node[10];
}
}
}
++
다른 분의 코드를 보니 우선순위 큐를 사용한 풀이가 있었다.
public void main() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
// 힙 만들어서 사전 순으로 정렬
PriorityQueue<String> pq = new PriorityQueue<>();
for (int j = 0; j < n; j++) {
pq.add(br.readLine());
}
// 사전 상에서 가장 빠른 문자열
String last = pq.poll();
String ans = "YES";
// 큐가 빌 때까지 하나씩 뽑으면서 바로 옆의 문자열끼리 비교
// abc, abcd, abd, ... 이런 순으로 정렬되니까 옆문자열끼리는
// 1. 접두사 포함 관계
// 2. 중간부터 다름
// 둘 중 하나임. 여기서 1번 관계가 있는지 찾아내야함
while(!pq.isEmpty()){
String now = pq.poll();
if (now.startsWith(last)){
ans = "NO";
break;
}
last = now;
}
sb.append(ans+"\n");
}
System.out.print(sb);
}이 방식이 훨씬 간단하고 빠른 것 같다
느낀점
- 문자열 문제라 무조건 트라이만 떠올렸었는데 다른 자료구조를 이용해도 충분히 빠르게 풀 수 있다는 것을 느꼈다.