[Trie] 전화번호 목록 - Java

문제 바로가기

코딩테스트 연습 - 전화번호 목록

 

풀고 나니 이 문제랑 거의 똑같네용

마찬가지로 Trie로 풀었습니다.

import java.util.*;

class Solution {
    static class TrieNode {
		Map<Character, TrieNode> childNodes = new HashMap<>();
		boolean isLastChar;
	}

	static class Trie {
		TrieNode root = new TrieNode();

		void insert(String input) {
			TrieNode cur = root;

			for (int i = 0; i < input.length(); i++) {
				char ch = input.charAt(i);
				if (cur.childNodes.containsKey(ch) == false) {
					cur.childNodes.put(ch, new TrieNode());
				}
				cur = cur.childNodes.get(ch);
			}
			cur.isLastChar = true;
		}

		boolean check(String input) {
			TrieNode cur = root;

			for (int i = 0; i < input.length(); i++) {
				char ch = input.charAt(i);
				if (cur.isLastChar == true && cur.childNodes.get(ch) != null) return false;
				cur = cur.childNodes.get(ch);
			}

			return true;
		}
	}

	public boolean solution(String[] phone_book) {
		Trie trie = new Trie();
        
        // 트라이 생성
		for (String pb : phone_book) {
			trie.insert(pb);
		}
        
        // 접두어 체크
		for (String pb : phone_book) {
			if (trie.check(pb) == false) return false;
		}

		return true;
	}
}

사실 startsWith() 로도 풀 수 있습니다. 하지만 트라이 연습 겸 짜보았슴니다.

// startsWith() 사용
import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
		for (String pb : phone_book) {
			for(int i = 0; i < phone_book.length; i++) {
				if(phone_book[i].equals(pb)) continue;
				if(phone_book[i].startsWith(pb)) return false;
				if(pb.startsWith(phone_book[i])) return false;
			}
		}

		return true;
	}
}

 

먼저 TrieNode 클래스의 멤버 변수로는 Map<Character, TrieNode> 로 자식 노드들을 표현했고, 접두어인지 판별하기 위해 isLastChar 라는 boolean 변수를 가집니다.

 

insert() 메소드에서는 문자열을 입력받아서 Trie를 만들어주고, 맨 마지막 문자 여부를 추가해줍니다.

그리고 check() 메소드에서는 똑같이 문자열을 입력받으면서 isLastChar가 true 이면서 자식 노드를 가지면 이는 누가 누군가의 접두어라는 의미가 되므로 false 를 리턴해줍니다.

 

 

감사합니다!!