프로그래머스 가사 검색 (JAVA)

2020 KAKAO BLIND RECRUITMENT

---

길찾기 게임

---

 

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

 

보통 이런 문제의 경우, 와일드카드 문자, 만능 문자 등의 단어가 들어가는 문제의 경우는 대부분 트라이(Trie) 알고리즘을 겨냥해서 만들어진 문제라고 생각한다. 보통은 조합으로 HashMap에 전부 넣고나서 사용하는 방식을 더 선호하지만(구현이 간단하므로) 이 문제는 트라이를 구현하지않으면 효율성에서 문제가 발생하는 문제였으므로, 트라이 알고리즘을 구현하여 풀었다.

 

특별히 주석이 필요할만한 부분은, 

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

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

이 부분이다. 본래는 이 부분에서 children으로 넘어가서 다음 노드를 만들기위해서 코드가 조금 복잡해졌었는데, 아예 node.children을 사용하는 것으로 심플하게 코드를 구현할 수 있었다.

 

computeIfAbsent에 대해 익숙하지 않은 분들은, 키 값이 존재하지 않는 경우에 초기값을 생성해주는 메서드라고 생각하시면 될 것 같다.

자매품으로 merge, computeIfPresent 등이 있는데, 개인적으로 merge를 정말 많이 사용하므로, 사용해보지 않은 분들은 한번 공부해보시길 추천한다.

 

import java.util.*;
class Solution {
   	public static int[] solution(String[] words, String[] queries) {
		Trie[] tries = new Trie[100001];
		for (String word : words) {
			int len = word.length();
			if (tries[len] == null)
				tries[len] = new Trie();
			tries[len].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;
	}

	static class Trie {
		Node front;
		Node back;

		Trie() {
			this.front = new Node();
			this.back = new Node();
		}

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

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

		private void insertBack(String word) {
			Node node = back;
			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) == '?')
				return getCountFromBack(query);
			else
				return getCountFromFront(query);
		}

		private int getCountFromFront(String query) {
			Node node = front;
			for (int i = 0; i < query.length(); i++) {
				if (query.charAt(i) == '?')
					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 = back;
			for (int i = query.length() - 1; i >= 0; i--) {
				if (query.charAt(i) == '?')
					break;
				if (!node.children.containsKey(query.charAt(i)))
					return 0;
				node = node.children.get(query.charAt(i));
			}
			return node.count;
		}

	}

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

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