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

 

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

5052번: 전화번호 목록

난이도 : 골드 4

 

트라이를 이용했습니다.

2021/01/07 - [문제풀이/자바] - [백준 14725] 개미굴 (자바)

[백준 14725] 개미굴 (자바)

트라이 String 버전

---

함수

void main

입력을 받고 트라이를 구성합니다.

한 개의 입력을 처리할 때 어느 입력의 끝을 지나면 일관성이 없으므로 "NO"를 StringBuilder에 추가합니다. (28번째 줄)

입력을 트라이에 넣을 때 항상 입력의 마지막을 체크해줍니다. (55번째 줄)

 

class Trie

word는 이 트라이가 입력의 끝인지를 나타냅니다. n은 트라이의 숫자입니다.

al은 다음으로 이어지는 값입니다.

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	public class p5052 {
	public static void main(String[] args) throws Exception{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int tc = Integer.parseInt(br.readLine());
	StringBuilder sb = new StringBuilder();
	//테스트 케이스
	while(tc --> 0) {
	int n = Integer.parseInt(br.readLine());
	Trie trie = new Trie(-1);
	boolean pass = false;
	//입력 수
	while(n --> 0) {
	String input = br.readLine();
	Trie node = trie;
	if(pass)
	continue;
	//한 입력 처리
	for(int i = 0; i < input.length(); i++) {
	int now = input.charAt(i) - '0';
	if(node.word) {
	sb.append("NO").append("\n");
	pass = true;
	break;
	}
	else {
	int index = -1;
	for(int j = 0; j < node.al.size(); j++) {
	if(node.al.get(j).n == now) {
	index = j;
	break;
	}
	}
	if(index == -1) {
	node.al.add(new Trie(now));
	node = node.al.get(node.al.size()-1);
	}
	else {
	node = node.al.get(index);
	if(i == input.length()-1) {
	sb.append("NO").append("\n");
	pass = true;
	break;
	}
	}
	if(i == input.length()-1)
	node.word = true;
	}
	}
	}
	if(!pass)
	sb.append("YES").append("\n");
	}
	System.out.println(sb.toString());
	}
	static class Trie{
	boolean word;
	int n;
	ArrayList<Trie> al;
	Trie(int n) {
	this.n = n;
	al = new ArrayList<>();
	word = false;
	}
	}
	}

view raw p5052.java hosted with ❤ by GitHub