[백준 5670번] 휴대폰 자판 (java)

5670번: 휴대폰 자판

 

이번 문제를 트라이를 이용하여 풀 수 있는 문제이다.

Trie 의 insert, contain, delete 함수외에 검색횟수를 반환하는 별도의 getCount() 함수를 만들어서 문제를 해결하였다.

 

트라이 알고리즘에 대해 잘 모른다면 아래 링크를 참조하길 바란다.

lotuslee.tistory.com/53?category=965898

트라이(Trie) - 1. 트라이 개념 및 노드 특징

 

문제 예제에서 hell, hello, heaven, goodbye 4개의 단어가 존재한다.

이 경우 트라이 구조를 나타내면 아래와 같이 표현할 수 있다.

 

 

hell을 검색하는 경우, 우선 첫글자인 'h'를 입력한다. 'h'로 시작하는 단어들은 모두 hell, hello, heaven 이렇게 3개가 있다. 그런데 3가지 모두 'h' 다음에 'e' 가 오기 때문에 모듈은 알아서 'e'를 입력해준다.

왜냐하면 'e'이외의 다른 선택지가 없기 때문이다. 이렇게 특정 문자 다음에 오는 문자가 하나밖에 없으면 그 때는 모듈이 알아서 입력을 해주기 때문에 직접 입력할 필요가 없다.

 

트라이 알고리즘에서 이러한 경우는 어떻게 판단할 수 있을까?

현재 노드의 자식 노드 개수로 알 수 있다. 만약 현재 노드의 자식 노드가 하나밖에 없다면,

이는 특정 문자 다음에 오는 문자가 하나밖에 없다는 뜻과 같다. 따라서 이럴 경우에는 사용자가 버튼을 누를 필요가 없다.

 

'e' 다음의 문자를 보자. 'he'로 시작하는 단어는 hell, hello, heaven  3개이다. 'e' 다음에 가능한 문자가 'a', 'l' 두 가지가 있다. 따라서 모듈이 자동으로 입력해줄 수 없다. 즉, 사용자가 버튼을 눌러야 한다.

 

'l'은 사용자가 직접 입력했다. 'hel'로 시작하는 단어는 hell, hello 2개이다. 'l' 다음에 오는 문자는 'l' 하나뿐이므로 모듈이 자동으로 입력해준다. 

 

정리하면, hell 단어를 검색하는 과정은 다음과 같다.

'h'(1) -> 'e'(0) -> 'l'(1) -> 'l'(0)

(괄호 안의 수가 1이면 사용자가 검색)

hell 단어를 검색하기 위해 총 두 번 사용자가 버튼을 눌러야 한다.

 

 

hello의 경우도 마찬가지로 'hel' 까지는 hell 단어와 검색 과정이 동일하다. 'h'(1) -> 'e'(0) -> 'l'(1) 

이제 두번째 'l'을 보자. 위의 트라이 구조를 보면 'l' 다음에 오는 자식 노드는 'o' 하나밖에 없다.

그런데 위에서 설명한 데로라면 'l'의 자식 노드는 'o' 하나뿐이므로 사용자가 버튼을 누를 필요가 없게 된다.

하지만 생각해보면 hello를 검색하기 위해서는 hell까지 입력한 후, o를 사용자가 직접 입력해야 한다.

왜냐하면 hell까지만 입력을 하면 사용자가 hell이라는 단어를 검색하려고 하는 것인지, hello라는 단어를 검색하려고 하는것인지 모듈은 구분할 수 없기 때문이다.

 

즉, 검색하려는 단어에 포함되는 특정 문자가 또 다른 단어의 마지막 문자라면(isLastChar = true)

이 경우에는 사용자가 직접 버튼을 눌러야 한다.

'h'(1) -> 'e'(0) -> 'l'(1) -> 'l'(0) -> 'o'(1)

 

여태까지 설명한 것을 바탕으로 getCount() 메서드를 만들면 다음과 같다.

public int getCount(String word) {

		int cnt = 1; // 첫 문자는 무조건 사용자가 직접 입력
		TrieNode thisNode = rootNode;

		for (int i = 0; i < word.length(); i++) {
			char ch = word.charAt(i);
			thisNode = thisNode.getChildNodes().get(ch);

			// 아직 단어 검색이 완료되지 않았으면서
			// 특정 문자가 다른 단어의 마지막 문자이거나(isLastChar = true)
			// 현재 노드의 자식 노드가 1개 이상일 경우,
			// 사용자가 문자를 직접 입력한다. (cnt 증가)
			if (i < word.length() - 1 && (thisNode.isLastChar() || thisNode.getChildNodes().size() > 1))
				cnt++;
		}

		return cnt;
}

 

 

정답코드 :