Menu

Subscribe

[JAVA/프로그래머스] 2020 KAKAO BLIND RECRUITMENT: 가사 검색

HEESOO on Programmers

👀 문제

https://programmers.co.kr/learn/courses/30/lessons/60060

👊 도전

1. 설계

  1. 자료구조 트라이(Trie)를 이용하여 문제를 해결한다.
  2. word를 처음부터 저장하는 트라이 하나와, 뒤에서부터 저장하는 트라이 하나를 만든다.
  3. query가 ?로 시작하면 뒤에서부터 저장한 트라이를 탐색해 일치하는 단어의 개수를 리턴하고, ?로 끝나면 처음부터 저장한 트라이를 탐색한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

import java.util.HashMap;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
   public 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;
	}
}
class Trie{
	Node front, back;
	
	public 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;
	}
}
class Node{
	HashMap<Character, Node> children;
	int count;
	
	public Node(){
		this.children=new HashMap<>();
		this.count=0;
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. Node 클래스를 만든다
    • Node는 트라이에 사용된다.
    • 하나의 노드는 자식을 가지며, 이때 자식은 영문자 a~z중 하나로 탐색 시간을 줄이기 위해 HashMap을 사용한다.
    • 루트에서 현재 노드까지의 깊이를 count에 저장한다.
  2. Trie 클래스를 만든다
    • 실행결과
    • 트라이는 word를 처음부터 저장하는 것 하나(front)와, 뒤에서부터 저장하는 것(back) 하나를 둔다.
    • query가 “?”로 시작하면 back을 탐색하면 되고, “?”로 끝나면 front를 탐색한다.
    • 따라서, insert()가 호출되었을 때, front와 back에 모두 word를 삽입한다.
    • insertFront(): 시작 루트가 front이므로 node를 front로 초기화한다. 현재 노드까지 일치하는 문자열이 하나 더 생긴 것이므로 node.count++한다. word의 문자를 하나씩 확인하며 해당 문자가 front에 해당 노드의 children인 HashMap에 들어가 있지 않다면(computeIfAbsent) key는 word.charAt(i), value는 new Node()를 만든 후, 해당 node로 이동한다.
    • getCount(): query가 ?로 시작하면 뒤에서부터 탐색하고, 아니면 앞에서부터 탐색한다.
    • getCountFromFront(): query에 물음표가 뒤에 있는 경우이다. 따라서 query의 문자를 하나씩 확인하며, 물음표가 나온 경우 지금까지의 노드 개수를 리턴한다. 또는, 현재 query의 문자가 존재하지 않을 경우 0을 리턴한다.
    • solution(): tries의 인덱스는 query의 길이를 뜻한다. 예를 들어 query 길이가 5인 문자들은 모두 tries[5]에서 저장된다. query의 길이는 100,000이하이므로 배열의 길이는 100,001이어야 한다.

👏 해결 완료!

참고