공부 기록

풀이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;
	}
}

원래 풀이는 for문을 돌며 쿼리에 매칭되는 word의 수를 하나하나 구하도록 했다.

시간 복잡도는 O(쿼리 길이 X 쿼리 갯수 X 워드 갯수)로 효율성 테스트 1, 2, 3 을 통과하지 못했다. 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		String words[] = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
		String queries[] = { "fro??", "????o", "fr???", "fro???", "pro?" };
		Solution solution = new Solution();
		int[] answer = solution.solution(words, queries);
		for (int i = 0; i < answer.length; i++) {
			System.out.println(answer[i]);
		}
	}
}

class Solution {
	public static char WILD_CARD = '?';

	public int[] solution(String[] words, String[] queries) {
		int queryLength = queries.length;
		int[] answer = new int[queryLength];

		for (int i = 0; i < queryLength; i++) {
			answer[i] = matchedQuery(queries[i], words);
		}

		return answer;
	}

	public int matchedQuery(String query, String[] words) {
		int answer = 0;
		for (int i = 0; i < words.length; i++) {
			if (isMatched(query, words[i])) {
				answer++;
			}
		}

		return answer;
	}

	public boolean isMatched(String query, String word) {
		if (query.length() != word.length()) {
			return false;
		}

		for (int i = 0; i < query.length(); i++) {
			if (query.charAt(i) != word.charAt(i)) {
				if (query.charAt(i) != WILD_CARD && word.charAt(i) != WILD_CARD) {
					return false;
				}
			}
		}
		return true;
	}
}

이 문제는 특수한 자료구조를 사용하여 문제를 풀어야 한다.

바로바로~~ trie

[Trie 자료구조]

Trie 자료구조란?

• 텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조이다.

Trie 자료구조의 형태는?

• 각 노드는 <Key, Value> 맵을 가지고 있다. Key는 하나의 알파벳이 되고, Value는 그 Key에 해당하는 자식 노드가 된다.
• 다음은 DEV, DEAR, PIE, POP, POW라는 단어가 들어있는 Trie 자료구조를 도식화한 것이다. 휴대폰 전화번호부에서 검색을 하거나 사전에서 단어를 찾는 것과 같다.
• 예를 들어, 아래 그림에서 'DEV’라는 문자열을 찾으려면 루트 노드에서부터 순차적으로 [D] -> [E] -> [V] 를 탐색한다.

• 그림에서 볼 수 있듯이 루트 노드는 특정 문자를 의미하지 않고, 자식 노드만 가지고 있다.
• 유의할 점은 '부모 노드’나 '자신이 어떤 알파벳(Key)에 해당하는 노드(Value)'인지를 가지고 있는게 아니라는 점

• 즉, 루트 노드는 [D], [P]라고 하는 알파벳을 Key로 하는 자식 노드들을 가지고 있고, [D]는 [E]를 Key로 하는 자식 노드, [P]는 [I]와 [O]를 Key로 하는 자식 노드들을 가지고 있는 것이다.
• 또 루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다는 특징이 있다. 즉, ‘DE’ 노드의 자손인 'DEAR’와 'DEV’는 'DE-'를 공통 접두어로 가지며, 'P’의 자손인 'POW’와 'PIE’는 'P-'를 공통 접두어로 가진다.

Java에는 Trie가 라이브러리로 없기 때문에 직접 구현해줘야 한다.

이때 쿼리가 "??odo", "fro??", "?????" 등의 형태이므로

1. front에서 검색 / back에서 검색할 수 있도록 구현해야 한다.

2. 그리고 단어의 길이에 따라 알맞은 단어를 검색 할 수 있도록 해야 한다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		String words[] = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
		String queries[] = { "fro??", "????o", "fr???", "fro???", "pro?" };
		Solution solution = new Solution();
		int[] answer = solution.solution(words, queries);
		for (int i = 0; i < answer.length; i++) {
			System.out.print(answer[i] + " ");
		}
	}
}

class Solution {

	public int[] solution(String[] words, String[] queries) {

		Trie[] tries = new Trie[100001];
		for (String word : words) {
			int wordLength = word.length();
			if (tries[wordLength] == null) {
				tries[wordLength] = new Trie();
			}

			tries[wordLength].insert(word);
		}

		int[] answer = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			int len = queries[i].length();
			if (tries[len] == null) {
				answer[i] = 0;
			} else {
				answer[i] = tries[len].getCount(queries[i]);
			}
		}
		return answer;
	}
}

class Trie {
	public static char WILD_CARD = '?';

	private Node frontRootNode;
	private Node backRootNode;

	Trie() {
		frontRootNode = new Node();
		backRootNode = new Node();
	}

	public void insert(String word) {
		insertFront(word);
		insertBack(word);
	}

	private void insertFront(String word) {
		Node node = frontRootNode;
		for (int i = 0; i < word.length(); i++) {
			node.count++;
			// word.charAt(i) 가 children에 없는 경우 새로운 Node를 만든다.
			node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
		}
	}

	private void insertBack(String word) {
		Node node = backRootNode;
		for (int i = word.length() - 1; i >= 0; i--) {
			node.count++;
			node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
		}
	}

	public int getCount(String query) {
		if (query.charAt(0) == WILD_CARD) {
			return getCountFromBack(query);
		}

		return getCountFromFront(query);
	}

	private int getCountFromFront(String query) {
		Node node = frontRootNode;

		for (int i = 0; i < query.length(); i++) {
			if (query.charAt(i) == WILD_CARD) {
				break;
			}
			if (!node.children.containsKey(query.charAt(i))) {
				return 0;
			}
			node = node.children.get(query.charAt(i));
		}
		return node.count;
	}

	private int getCountFromBack(String query) {
		Node node = backRootNode;

		for (int i = query.length() - 1; i >= 0; i--) {
			if (query.charAt(i) == WILD_CARD) {
				break;
			}
			if (!node.children.containsKey(query.charAt(i))) {
				return 0;
			}
			node = node.children.get(query.charAt(i));
		}
		return node.count;
	}

}

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

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

참고

https://woovictory.github.io/2020/04/22/Java-Trie/

https://leveloper.tistory.com/99