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

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

5052번: 전화번호 목록

Trie 자료구조를 사용해 문제를 해결하였다.

💡 computeIfAbsent()
Map에서 특정 키에 해당하는 값이 존재하는지 확인한 후, 없으면 새로 만들어서 넣어주는 형태의 코드이다.
Key값에 해당하는 value가 존재하면 가져와서 사용하고 없으면 새로 만들어주는 패턴의 코드를 위해 computeIfAbsent()라는 메소드를 이용할 수 있다.
전
Value value = map.get(key);
if(value == null) {
value = getNewValue(key);
map.puy(key, value);
}
후
Value value = map.computeIfAbsent(key, k -> getNewValue(key));

 

import java.io.*;
import java.util.*;

public class boj_5052 {
	static class Node{
		Map<Character, Node> childNode = new HashMap<>();
		boolean end;
	}
	static class MakeTrie{
		Node rootNode = new Node();
		boolean insert(String phone) {
			Node node = this.rootNode;
			boolean flag = false;
			for(int p=0; p<phone.length(); p++) {
				Node temp = node.childNode.getOrDefault(phone.charAt(p), null);
				if(temp == null) flag = true;
				node = node.childNode.computeIfAbsent(phone.charAt(p), key -> new Node());
				if(node.end) return false;
			}
			node.end = true;
			return flag;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(bf.readLine());
		for(int t=1; t<=T; t++) {
			int N = Integer.parseInt(bf.readLine());
			boolean flag = false;
			MakeTrie trie = new MakeTrie();
			for(int i=0; i<N; i++) {
				if(!trie.insert(bf.readLine())) flag = true;
			}
			if(flag) sb.append("NO").append("\\n");
			else sb.append("YES").append("\\n");
		}
		System.out.println(sb);
	}

}

MakeTrie class를 살펴보자

static class MakeTrie{
	Node rootNode = new Node();
	boolean insert(String phone) {
		Node node = this.rootNode;
		boolean flag = false;
		for(int p=0; p<phone.length(); p++) {
			Node temp = node.childNode.getOrDefault(phone.charAt(p), null);
			if(temp == null) flag = true;
			node = node.childNode.computeIfAbsent(phone.charAt(p), key -> new Node());
			if(node.end) return false;
		}
		node.end = true;
		return flag;
	}
}

1. flag 변수를 통해 해당 번호가 다른 번호의 접두사로 존재하는 지를 확인해준다.
2. for문을 통해 새로운 전화번호를 삽입한다.
3. 해당 번호가 다른 번호를 접두사로서 사용할 수 있으므로 node.end가 중간에 true인 경우 false를 return해준다.

main을 살펴보자

public static void main(String[] args) throws Exception{
	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	int T = Integer.parseInt(bf.readLine());
	for(int t=1; t<=T; t++) {
		int N = Integer.parseInt(bf.readLine());
		boolean flag = false;
		MakeTrie trie = new MakeTrie();
		for(int i=0; i<N; i++) {
			if(!trie.insert(bf.readLine())) flag = true;
		}
		if(flag) sb.append("NO").append("\\n");
		else sb.append("YES").append("\\n");
	}
	System.out.println(sb);
}

flag 변수를 통해서 insert 중 false가 발생한다면 flag를 true로 바꾼다.

flag가 true면 NO 아니면 YES를 출력