programmers.co.kr/learn/courses/30/lessons/60060
코딩테스트 연습 - 가사 검색
programmers.co.kr
[문제 설명]
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자 중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
가사 단어 제한사항
- words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
- 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
- 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
- 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드 제한사항
- queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
- 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
- 검색 키워드는 중복될 수도 있습니다.
- 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
- 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
- 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
- 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
[풀이]
각 가사 단어의 길이는 1이상 10,000 이하 문자열이면서, 전체 가사 단어 길이의 합은 2 이상 1,000,000 배열의 길이는 100,000까지 있다.
문자열을 찾는 문제는 다양한 방법으로 풀 수 있지만, 대량에 문자열 패턴 매칭은 Trie(트라이) 구조를 이용해서 해결할 수 있다. Trie는 검색 시 단어 자동완성 기능에도 사용한다.
Trie 구조이다. 포함된 글자는 직관적으로 봤을 때 abcf, abd, avq 세 가지가 있다. ab를 넣어도, abc를 넣어도 각 알파벳의 카운트만 증가할 뿐, 트라이구조는 같을 것이다.
이 위의 상태에서 Trie구조에 카운터를 추가할 것이다. 단어는 abcf, abd, avq만 있다고 가정한다.
이렇게만 구현하면 a만 나와도 a로 시작하는 단어가 3개가 있다는 것을 알 수 있다.
하지만 문제는 이런 식으로 물어보는 게 아니다.
?라는 와일드 카드가 접두사, 접미사에 붙을 수 있다는 것이다.
위의 트리 구조에서 av?라는 쿼리에 대한 답을 낼 때, 우리는 q까지 가지 안아도 v에 카운트가 1인 것을 확인하고 1을 리턴해줄 수 있다.
하지만 ab?라면? 2개를 반환할 것이다. 답은 1인데도 말이다.
그래서 우리는 Trie구조를 각 word의 글자 수 만큼 만들어야 한다.
물론 저 Trie구조에 효율적인 로직을 구현하여 답을 풀 수 있을 것이다. 푸는 방법은 다양하니 개성에 맞게 풀자.
위와 같은 트라이 구조가 100,000개가 나올 수 있다.(단어 길이는 1부터 100,000까지니까)
코드를 보며 이해할 분들을 위해 코드에 사용한 트라이 구조를 이미지화 해보겠다.
하나의 TrieNode 안에는 Map이 있다. Map은 Character와 TrieNode로 구성돼있다.
추가적으로 정말 많은 데이터에 쿼리문 시작이 ?로 시작한다면 많은 데이터들을 비교해야 할 것이다. 방지하기 위해 word를 거꾸로 저장하는 역방향 Trie구조도 필요하다.
ex) wor? 는 wor까지만 검색하고 count를 찾으면 되지만 ?ord는 a-z까지 있는 것은 모두 가봐야 하기 때문에 dro?라는 쿼리로 drow를 검색하는 것이 낫다. (원문 : word)
[코드]
|
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
public int[] solution(String[] words, String[] queries) {
//각 words의 길이마다 트라이구조를 만들고,
//트라이 구조를 만들 때 해당 길이의 트라이는 정방향, 뒷방향 두개를 만들어준다.
//나누는 이유는 접두사로 ?이 왔을 때 검색해야하는 경우의 수가 너무 많기 때문에 뒤에서부터 찾기위함이다.
Trie[] trie = new Trie[100001]; //100000개의 길이를 갖을 수 있기 때문에
for(int i = 0; i < words.length; i++) {
int wordLen = words[i].length();
if(trie[wordLen] == null) {
trie[wordLen] = new Trie();
}
trie[wordLen].insert(words[i]);
}
int[] answer = new int[queries.length];
for(int i = 0; i < queries.length; i++) {
int queryLen = queries[i].length();
if(trie[queryLen] == null) {
answer[i] =0;
continue;
}
answer[i] = trie[queryLen].getCount(queries[i]);
}
return answer;
}
class Trie{
TrieNode forward;
TrieNode back;
Trie(){
forward = new TrieNode();
back = new TrieNode();
}
public void insert(String words) {
insertBack(words);
insertForward(words);
}
private void insertBack(String words) {
TrieNode node = back;
for(int i = words.length() - 1; i >= 0; i--) {
node.count++;
if(!node.childNodes.containsKey(words.charAt(i))){
node.childNodes.put(words.charAt(i), new TrieNode());
}
node = node.childNodes.get(words.charAt(i));
}
}
private void insertForward(String words) {
TrieNode node = forward;
for(int i = 0 ; i < words.length(); i++) {
node.count++;
if(!node.childNodes.containsKey(words.charAt(i))){
node.childNodes.put(words.charAt(i), new TrieNode());
}
node = node.childNodes.get(words.charAt(i));
}
}
public int getCount(String query) {
if(query.charAt(0) == '?') { //접두사
return getCountBack(query);
}
return getCountForward(query);
}
private int getCountBack(String query) {
TrieNode node = back;
for(int i = query.length() - 1; i >= 0 ; i--) {
if(query.charAt(i) =='?') {
return node.count;
}
if(!node.childNodes.containsKey(query.charAt(i))) {
return 0;
}
node = node.childNodes.get(query.charAt(i));
}
return node.count;
}
private int getCountForward(String query) {
TrieNode node = forward;
for(int i = 0; i < query.length(); i++ ){
if(query.charAt(i) =='?') {
return node.count;
}
if(!node.childNodes.containsKey(query.charAt(i))) {
return 0;
}
node = node.childNodes.get(query.charAt(i));
}
return node.count;
}
}
class TrieNode{
int count;
Map<Character, TrieNode> childNodes;
public TrieNode() {
count = 0;
childNodes = new HashMap<Character, TrieNode>();
}
}
|
cs |
느낀 점: 처음에는 패턴매칭으로 찾으려고 노력했다. 하지만 효율성 3개를 남겨두고 못한다고 확신했을 때, 트라이 구조로 풀 수 있다는 것을 검색을 통해 알아냈고, 트라이 공부와 해당 로직을 구현하는 것도 다른 분의 블로그로 참고했다.
'코딩테스트 > 2020 블라인드 코딩 테스트' 카테고리의 다른 글
| [2020 KAKAO BLIND RECRUITMENT][1차] 문자열 압축 for JAVA (0) | 2020.09.10 |
|---|---|
| [2020 KAKAO BLIND RECRUITMENT][1차] 괄호 변환 for JAVA (0) | 2020.09.10 |
| [2020 KAKAO BLIND RECRUITMENT][1차] 자물쇠와 열쇠 for JAVA 재업로드 (0) | 2020.09.10 |
| [2020 KAKAO BLIND RECRUITMENT][1차] 문자열 압축 for PYTHON (0) | 2020.06.15 |
| [2020 KAKAO BLIND RECRUITMENT][1차] 자물쇠와 열쇠 for JAVA (0) | 2020.04.02 |