Programmers 17685: 자동완성

풀이1) Trie 자료구조

1. Trie 자료구조 구현

    - Node 필드 정의: character, 해당 prefix를 가지는 단어의 수

2. Node를 따라가면서 해당 단어의 count = 1일때 멈춘다.

 

 

 

 

 

 

 

 

 

로직을 대충 생각해보니까 굳이 Trie 자료구조가 필요없을 것 같으나...

그래도 한번 구현해 보는 것이 좋을 것 같아서 아래와 같이 짜봤다.

 

import java.util.*;
class Solution {
	public int solution(String[] words) {
		Trie trie = new Trie();
		for (String word : words) {
			trie.insert(word);
		}

		int answer = 0;
		for (String word : words) {
			answer += trie.searchWordFromFront(word);
		}

		return answer;
	}
}

class Trie {
	private Node rootNode;

	Trie() {
		rootNode = new Node();
	}

	public void insert(String word) {
		Node node = rootNode;
		for (int i = 0; i < word.length(); i++) {
			node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
			node.count++;
		}
	}

	public int searchWordFromFront(String word) {
		Node node = rootNode;
		int move = 0;
		for (int i = 0; i < word.length(); i++) {
			node = node.children.get(word.charAt(i));
			move++;

			if (node.count == 1) {
				break;
			}
		}

		return node.count == 1 ? move : word.length();
	}
}

class Node {
	Map<Character, Node> children;
	int count;

	Node() {
		this.children = new HashMap<>();
		this.count = 0;
	}
}

 

풀이2) 정렬 후 인접하는 두 단어 비교

만약 두 단어 before, word가 0 이상 길이의 동일한 prefix를 가진다고 하면, before을 찾기 위해서는

1. before과 word가 같은 서브트리에 존재

   - before.length > prefix.length : prefix+1개 입력

   - before.length == prefix.length : prefix개 입력

2. before과 word가 다른 서브트리에 존재

   - prefix+1개 입력

class Solution {
	public int solution(String[] words) {
		Arrays.sort(words);
		String before = "";
		int beforePressCount = 1;
		int beforeSameCount = 0;
		int answer = 0;

		for (String cur : words) {
			int sameCount = 0;
			boolean isSimilar = false;

			// 이전 단어와 동일한 prefix 길이 구하기
			for (int i = 0; i < before.length(); i++) {
				if (before.charAt(i) == cur.charAt(i)) {
					sameCount++;
					isSimilar = true;
				} else {
					break;
				}
			}

			if (isSimilar && sameCount >= beforeSameCount) {

				// before 단어에 대한 입력 수 업데이트
				answer -= beforePressCount;
				if (before.length() > sameCount) {
					answer += (sameCount + 1);
				} else if (before.length() == sameCount) {
					answer += sameCount;
				}

				// word 단어에 대한 입력 수 업데이트
				beforePressCount = sameCount + 1;
				answer += beforePressCount;
			} else {
				beforePressCount = sameCount + 1;
				answer += beforePressCount;
			}

			before = cur;
			beforeSameCount = sameCount;
		}

		return answer;
	}
}