[백준 5052] 전화번호 목록 (JAVA)

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

 

이번 포스팅에서는 ICPC에서 출제된 트라이를 사용하는 문제가 있어 한번 다뤄보도록 하겠다.

 

먼저 트라이에 대해 알고싶다면 하단의 링크를 참조하도록 하자.

 

 

https://0bliviat3.tistory.com/53

[자료구조] 트라이(Trie)의 구현 (JAVA)

 

 

그럼 바로 문제 분석으로 들어가도록 하겠다.

주어지는 전화번호 목록중 어떤 전화번호가 다른 전화번호의 접두사가 된다면

NO를 출력 모든 전화번호가 다른 번호들의 접두사가 아닌경우 YES를 출력해주면 되는 문제로

문제를 이해하는것 자체는 어렵지 않다.

 

 

그렇다면 주어지는 전화번호 목록을 어떻게 검사를 해야 접두사관계를 파악할수 있는건가..

 

아이디어는 전화번호길이의 내림차순 정렬이다.

 

주어지는 목록을 길이순으로 내림차순 정렬을한다면 조건에서

동일한 전화번호가 주어지는 경우는 없다 했으므로

긴 길이의 전화번호부터 우선적으로 트라이에 삽입

그리고 순차적으로 트라이에 삽입하는것이다.

 

이때 삽입과정중 현재 전화번호의 마지막 자리까지 삽입 완료된 상황이라고 가정해보자.

 

그런데 마지막자리의 노드가 자식 노드를 갖는 상황이라면,

이는 현재 전화번호가 이전에 삽입된 전화번호의 접두사라는 것을 의미하는것이다. 

 

따라서 이런 경우만 잡아주면 문제를 해결하는것엔 크게 어려움이 없을 것이다.

 

한가지 예를 들어 설명하자면

 

전화번호 목록이 [ 010 , 0101 ] 이렇게 존재 한다고 하면

길이순으로 내림차순 정렬한다면 [ 0101, 010 ] 으로 정렬이 될것이다. 

 

그리고 트라이에 순차적으로 삽입해보도록하겠다.

 

0101을 삽입해 자식노드에 대해서만 표현한다면 다음과 같은 그림이 나온다.

 

 

그리고 010을 삽입하게 된다면,

 

 

마지막 자리인 0까지 삽입이 완료된 상황일때 현재 노드에서 자식노드가 존재하게 된다.

이는 010이 0101의 접두사라는 것을 의미하게 되는것이다.

 

 

그렇다면 바로 코드로 구현해보도록 하겠다.

 

먼저 문자열길이에 따라 내림차순 정렬을 해주어야 하므로

정렬기준에 대해 재정의할 클래스를 하나 선언 해주도록 하겠다.

 

class CompareAttention implements Comparator<String> {

	@Override
	public int compare(String o1, String o2) {
		return o2.length() - o1.length();
	}
	
}

 

그리고 트라이를 구현하기 위해 트라이노드에 대한 클래스도 하나 선언해주도록 하겠다.

 

노드의 필드로는 자식노드배열을 갖고

입력받은 키값에 따라 자식노드 배열에 대한 메모리를 할당 후

이미 배열이 존재한다면, 해당 키값에 해당하는 자리에 객체를 생성하고

이미 객체가 존재한다면 다음 자릿수로 넘어갈 수 있도록

자식노드를 리턴해주는 add 메소드를 하나 선언해준다.

 

또 자식노드가 존재하는 지 판단할 hasmoreChild 메소드도 하나 선언해주도록 하겠다.

 

 

class CallNode {
	
	private CallNode[] child;
	
	CallNode add(char key) {
		int no = key - '0';
		if(child == null) { child = new CallNode[10]; }
		if(child[no] == null) { child[no] = new CallNode(); }
		return child[no];
	}
	
	boolean hasmoreChild() {
		return child == null;
	}
	
	
}

 

 

이제 트라이 클래스를 하나 선언할것이다.

 

필드로 루트노드를 하나 갖도록하고,

루트노드를 초기화해줄 메소드와

 

삽입메소드만 선언해준다.

 

이때 삽입메소드는 boolean 타입으로 리턴값을 주어 인자로 받는 문자열이 접두사라면

false를 리턴 아닌 경우 true를 리턴할 수 있도록 하겠다.

 

class CallTrie {
	
	private CallNode root;
	
	void init() {
		root = new CallNode();
	}
	
	boolean insert(String str) {
		int size = str.length();
		return insertProcess(root.add(str.charAt(0)),str,size,1);
	}
	
	private boolean insertProcess(CallNode node, String str, int size, int idx) {
		if(size == idx) { return node.hasmoreChild(); }
		return insertProcess(node.add(str.charAt(idx)),str,size,idx + 1);
	}
}

 

 

이제 입력형식에 맞게 입력을 받아 

정렬 후 각 테스트 케이스에 대한 출력값만 가져오면 된다.

 

해당 코드를 작성해 실행한다면 다음과 같이 정확한 답을 내는것을 확인 할 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Boj5052 {
	
	/*
	 * 제출 完
	 */
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(in.readLine());
		CallTrie trie = new CallTrie();
		while(t-- > 0) {
			int n = Integer.parseInt(in.readLine());
			String[] strArr = new String[n];
			for(int i = 0; i < n; i++) {
				strArr[i] = in.readLine();
			}
			Arrays.sort(strArr,new CompareAttention());
			trie.init();
			boolean flag = false;
			for(int i = 0; i < n; i++) {
				if(!trie.insert(strArr[i])) {
					flag = true;
					break;
				}
			}
			if(flag) {
				sb.append("NO\n");
			}else {
				sb.append("YES\n");
			}
				
		}
		
		in.close();
		
		System.out.print(sb);
	}

}

class CompareAttention implements Comparator<String> {

	@Override
	public int compare(String o1, String o2) {
		return o2.length() - o1.length();
	}
	
}

class CallNode {
	
	private CallNode[] child;
	
	CallNode add(char key) {
		int no = key - '0';
		if(child == null) { child = new CallNode[10]; }
		if(child[no] == null) { child[no] = new CallNode(); }
		return child[no];
	}
	
	boolean hasmoreChild() {
		return child == null;
	}
	
	
}

class CallTrie {
	
	private CallNode root;
	
	void init() {
		root = new CallNode();
	}
	
	boolean insert(String str) {
		int size = str.length();
		return insertProcess(root.add(str.charAt(0)),str,size,1);
	}
	
	private boolean insertProcess(CallNode node, String str, int size, int idx) {
		if(size == idx) { return node.hasmoreChild(); }
		return insertProcess(node.add(str.charAt(idx)),str,size,idx + 1);
	}
}