[BOJ] 전화번호 목록 5052.JAVA

문제 링크 : https://www.acmicpc.net/problem/5052

처음 전화번호 목록 문제를 접했을 때 이중 포문을 이용하여 시간 초과가 발생했다.

어떤 방법이 있을까 하고 고민할 때 스터디원이 Trie 자료구조를 사용하면 풀 수 있다고 힌트를 주었다.

하지만 Trie 자료구조를 모르고 있었기에 학습하여 문제를 해결하였고 Trie 자료구조를 이용하지 않더라도 풀 수 있는 방법이 있길래 Trie 자료구조를 사용하지 않는 방법으로 문제를 풀어보았다.

 

아래와 같이 소스를 공유한다.

 

Trie 자료구조를 이용한 구현

public class 전화번호목록 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int e = 0; e < T; e++) {
			int ca = Integer.parseInt(br.readLine());
			List<String> list = new ArrayList<>();
			Trie t = new Trie();
			
			for (int i = 0; i < ca; i++) {
				String word = br.readLine();
				list.add(word);
				t.insert(word);
			}
			
			boolean is = false;
			
			for(String k : list) {
				if(t.contains(k)) {
					is = true;
					break;
				}
			}
			
			sb.append((is == true) ? "NO":"YES").append("\n");
		}
		
        bw.write(sb.toString());
        bw.flush();
        bw.close();
	}
}

public class Trie {
	private TrieNode rootNode;
	
	public Trie() {
		this.rootNode = new TrieNode();
	}
	
	public void insert(String word) {
		TrieNode root = this.rootNode;
		
		for (int i = 0; i < word.length(); i++) {
			root = root.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
		}
		root.setIsLastChar(true);
	}
	
	public boolean contains(String word) {
		TrieNode temp = this.rootNode;
		
		for (int i = 0; i < word.length(); i++) {
			char ch = word.charAt(i);
			TrieNode node = temp.getChildNodes().get(ch);
			
			if(node == null) return false;
			
			temp = node;
		}
		
		if(temp.isLastChar()) {
			if(temp.getChildNodes().isEmpty()) {
				return false;
			}
		}
		
		return true;
	}
	
	public void delete(String word) {
		delete(this.rootNode, word, 0);
	}
	
	public void delete(TrieNode node, String word, int idx) {
		char ch = word.charAt(idx);
		
		if(!node.getChildNodes().containsKey(ch)) throw new Error(word + " : 존재하지 않습니다.");
		
		TrieNode child = node.getChildNodes().get(ch);
		idx++;
		
		if(idx == word.length()) {
			if(!child.isLastChar()) throw new Error(word + " : 존재하지 않습니다.");
			
			child.setIsLastChar(false);
			
			if(child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
		}else {
			delete(child, word, idx);
			
			if(!child.isLastChar() && child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
		}
	}
	
	public boolean isRootEmpty() {
		return this.rootNode.getChildNodes().isEmpty();
	}
}

public class TrieNode {
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	private boolean isLastChar;
	
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	
	boolean isLastChar() {
		return this.isLastChar;
	}
	
	void setIsLastChar(boolean is) {
		this.isLastChar = is;
	}
}

Trie 자료구조는 트리 형식으로 문자열을 찾는 자료구조이다.

Trie 자료구조를 이용하지 않은 구현

public class 전화번호목록 {
	public static Comparator<String> compare = new Comparator<>() {

		@Override
		public int compare(String o1, String o2) {
			return o1.compareTo(o2);
		}
		
	};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for (int e = 0; e < T; e++) {
			int c = Integer.parseInt(br.readLine());
			
			List<String> list = new ArrayList<>();
			
			for (int i = 0; i < c; i++) {
				list.add(br.readLine());
			}
			
			Collections.sort(list, compare);
			boolean is = false;
			for (int i = 1; i < c; i++) {
				if(list.get(i).startsWith(list.get(i-1))) {
					is = true;
					break;
				}
			}
			
			System.out.println((is == true) ? "NO":"YES");
		}
	}
}

주어지는 문자들을 정렬하고 startsWith 함수를 이용하여 비교한다.

 

 

문제를 푸는 방식이 다양하여 한 가지 문제를 풀더라도 여러 방법으로 풀어 다양한 접근 방식을 습득하려고 노력중이다.

 

---

참고 자료

• Trie 자료 구조 : the-dev.tistory.com/3

[자료구조] Trie(트라이)-2 : 자바로 구현하기

• blue-boy.tistory.com/189

[백준/5052번] 전화번호 목록(NCPC 2007)[Java]