programmers 60060: 가사 검색

원래 풀이는 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/

[Java] 트라이(Trie) 자료구조 개념

https://leveloper.tistory.com/99

[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 가사 검색 (Java)