백준 5052번 <전화번호 목록>

백준 알고리즘 5052번

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

5052번: 전화번호 목록

---

5052번

주어진 전화번호 목록이 있을 때, 해당 전화번호 중 전화를 걸 수 없는 번호가 있다면 NO를 모두 전화를 걸 수 있다면 YES를 출력하여라.

전화번호가 112, 112 345가 있다면 112 345에는 전화를 걸 수 없다. 112를 누르는 순간 112로 전화가 걸리기 때문에

 

입력으로 첫 줄에 테스트케이스의 개수 test가 들어오고 그 다음 줄부터 각 테스트케이스가 들어온다. 

테스트케이스는 전화번호의 개수 N이 들어오고 그 다음 N개의 줄에 전화번호가 들어온다.

 

출력으로 각 테스트케이스에 대하여 모든 전화번호에 전화를 걸 수 있다면 YES를 출력하고 그렇지 않다면 NO를 출력하면 된다.

---

문제 해결

처음에는 for문을 여러 개 써서 엄청난 풀이를 하려고 했는데 코딩 하는데 아무리 생각해도 아닌 거 같아서 다른 방법을 찾으려고 하였으나 찾지 못하고 구글링을 했다.

구글링해보니 Trie 자료구조를 이용하여 푸는 문제였다.

 

이 문제는 Trie 자료구조에 문자열을 insert할 때, 중간에 있는 문자를 마지막으로 하는 문자가 있으면 NO를 출력하면 되고 그렇지 않고 모든 문자열(전화번호)를 insert 할 수 있다면 YES를 출력하면 된다.

 

길이가 짧은 전화번호를 먼저 넣고 긴 전화번호를 넣어야 접두어가 같은 전화번호를 찾을 수 있기 때문에 Tuple 자료구조를 만들어서 문자열 전화번호와 long 형 전화번호를 모두 저장해두었다. 정렬은 long 형 전화번호를 기준으로 정렬하도록 하였다.

(처음에 int 형으로 저장했다가 error 남,,, 전화번호는 최대 10자리!!!)

---

코드

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 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int testcase = Integer.parseInt(br.readLine());
		for (int test = 0; test < testcase; test++) {
			int n = Integer.parseInt(br.readLine());
			Tuple[] number = new Tuple[n];
			for (int i = 0; i < n; i++) {
				String input = br.readLine();
				number[i] = new Tuple(Long.parseLong(input), input);
			}
			Arrays.sort(number);
			boolean chk = true;
			Trie trie = new Trie();
			for (int i = 0; i < n; i++) {
				boolean result = trie.insert(number[i].str);
				if (!result) {
					chk = false;
				}
				if (!chk) {
					break;
				}
			}
			if (!chk) {
				System.out.println("NO");
			} else {
				System.out.println("YES");
			}
		}

	}

}

class Tuple implements Comparable<Tuple> {
	long num;
	String str;

	public Tuple(long n, String s) {
		this.num = n;
		this.str = s;
	}

	public int compareTo(Tuple oth) {
		if (this.num > oth.num) {
			return 1;
		} else if (this.num == oth.num) {
			return 0;
		} else {
			return -1;
		}
	}
}

class TrieNode {
	private Map<Character, TrieNode> child = new HashMap<>();
	private boolean isLast;

	public Map<Character, TrieNode> getChild() {
		return this.child;
	}

	public boolean isLast() {
		return this.isLast;
	}

	public void setLast(boolean last) {
		this.isLast = last;
	}
}

class Trie {
	private TrieNode root;

	public Trie() {
		this.root = new TrieNode();
	}

	public boolean insert(String word) {
		TrieNode node = this.root;
		for (int i = 0; i < word.length(); i++) {
			node = node.getChild().computeIfAbsent(word.charAt(i), c -> new TrieNode());
			if (node.isLast()) {
				return false;
			}
		}
		node.setLast(true);
		return true;
	}
}

---

결과

---