문제 풀이/KAKAO BLIND RECRUITMENT
[2020 KAKAO BLIND RECRUITMENT] 가사 검색
hyeonic
2021. 1. 10. 23:33
코딩테스트 연습 - 가사 검색
programmers.co.kr
정확성과 효율성 테스트 각각 점수가 있는 문제이다.
가사 단어의 제한사항
- words의 길이(가사 단어의 개수)는 2 이상 100,000 이하이다.
- 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없다.
- 전체 가사 단아 길이의 합은 2 이상 1,000,000 이하이다.
- 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공된다.
- 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정한다.
검색 키워드 제한사항
- queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하이다.
- 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없다.
- 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이다.
- 검색 키워드는 중복될 수도 있다.
- 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정한다.
- 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어진다.
입출력 예시
| words | queries | result |
| ["frodo", "front", "frost", "frozen", "frame", "kakao"] | ["fro??", "????o", "fr???", "fro???", "pro?"] | [3, 2, 4, 1, 0] |
입출력 예에 대한 설명
- "fro??"는 "frodo", "front", "frost"에 매치되므로 3이다.
- "????o"는 "frodo", "kakao"에 매치되므로 2이다.
- "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4이다.
- "fro???"는 "frozen"에 매치되므로 1이다.
- "pro?"는 매치되는 가사 단어가 없으므로 0 이다.
효율성을 생각하지 않고 우선 답을 맞추기 위해 풀어보았다.
import java.util.Arrays;
public class SearchLyrics {
static class Solution {
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int count = 0;
for (int j = 0; j < words.length; j++) {
if (queries[i].length() != words[j].length()) continue;
else {
boolean isMatch = true;
for (int k = 0; k < queries[i].length(); k++) {
if (queries[i].charAt(k) != '?' && queries[i].charAt(k) != words[j].charAt(k)) {
isMatch = false;
break;
}
}
if (isMatch) ++count;
}
}
answer[i] = count;
}
return answer;
}
}
public static void main(String[] args) {
String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
String[] queries = {"fro??", "????o", "fr???", "fro???", "pro?", "?????"};
System.out.println(Arrays.toString(new Solution().solution(words, queries)));
}
}
간단하게 해결할 수 있었지만 for문을 세번 돌기 때문에 수행시간에서 통과하지 못하였다.
교수님의 특강 풀이를 활용하여 다시 한번 문제에 접근하였다. 길이 별로 Map에 모아서 query와 길이가 같은 단어들만 비교하도록 수정하였다.
import java.util.*;
public class SearchLyrics {
static class Solution {
Map<Integer, List<String>> split(String[] words) {
Map<Integer, List<String>> map = new HashMap<>();
for (String word : words) {
List<String> list = map.get(word.length());
if (list == null) {
list = new ArrayList<String>();
map.put(word.length(), list);
}
list.add(word);
}
return map;
}
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
Map<Integer, List<String>> map = split(words);
for (int i = 0; i < queries.length; i++) {
String query = queries[i];
int count = 0, start = 0, end = 0, length = query.length();
for (; start < length && query.charAt(start) == '?'; ++start);
for (end = start; end < length && query.charAt(end) != '?'; ++end);
query = query.substring(start, end);
List<String> list = map.get(length);
if (list != null)
for (String word : list)
if (query.equals(word.substring(start, end)))
++count;
answer[i] = count;
}
return answer;
}
}
public static void main(String[] args) {
String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
String[] queries = {"fro??", "????o", "fr???", "fro???", "pro?", "?????"};
System.out.println(Arrays.toString(new SearchLyrics_1.Solution().solution(words, queries)));
}
}
?가 시작하는 인덱스와 끝나는 인덱스를 찾아서 query를 substring 해준다. 각각의 단어 길이별로 구별한 map에 담아서 값을 구했지만 크게 성능개선이 이루어지지 않았다. 추가적인 자료구조나 알고리즘이 필요한 것으로 예상된다.
Trie 자료구조 - 보충 예정
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 트리의 루트에서 자식들을 따라가면서 생성된 문자열 들이 트라이 자료구조에 저장된다.
public class SearchLyrics_trie_1 {
static class Node {
Node[] nodes;
public void add(String word, int index) {
if (index == word.length()) return; // index 가 범위를 벗어났다.
if (nodes == null) nodes = new Node[26]; // 알파벳 숫자 만큼 자식 노드를 만든다.
int c = word.charAt(index) - 'a'; // word 에서 index 위치 문자가 'a' 이면 0 번째
// 'b' 이면 1 번째, 'c' 이면 2 번째 자식 노드이어야 한다.
if (nodes[c] == null) nodes[c] = new Node();
nodes[c].add(word, index + 1);
}
public void print(String s) {
if (nodes != null) { // 아직 leaf 노드가 아니다.
for (int i = 0; i < nodes.length; i++) // 자식 노드 재귀 호출 해야 한다.
if (nodes[i] != null)
nodes[i].print(s + (char)('a' + i)); // 현재 노드의 문자를 더해서, 자식 노드 재귀호출
} else // leaf
System.out.println(s); // leaf 이다. 단어가 하나 완성되었다.
}
}
static Node root = new Node();
public static void main(String[] args) {
String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
for (String word : words) {
root.add(word, 0);
}
root.print("");
}
}
frame
frodo
front
frost
frozen
kakaotrie가 잘 만들어 진것을 확인 할 수 있다.
public class SearchLyrics_trie_2 {
static class Node {
int count;
Node[] nodes;
public void add(String word, int index) {
++count;
if (index == word.length()) return; // index 가 범위를 벗어났다.
if (nodes == null) nodes = new Node[26]; // 알파벳 숫자 만큼 자식 노드를 만든다.
int c = word.charAt(index) - 'a'; // word 에서 index 위치 문자가 'a' 이면 0 번째
// 'b' 이면 1 번째, 'c' 이면 2 번째 자식 노드이어야 한다.
if (nodes[c] == null) nodes[c] = new Node();
nodes[c].add(word, index + 1);
}
public void print(String s) {
if (nodes != null) { // 아직 leaf 노드가 아니다.
for (int i = 0; i < nodes.length; i++) // 자식 노드 재귀 호출 해야 한다.
if (nodes[i] != null)
nodes[i].print(s + (char)('a' + i)); // 현재 노드의 문자를 더해서, 자식 노드 재귀호출
System.out.printf("중간: %s %d\n", s, count); // 중간노드의 자식 leaf 의 수 출력
} else // leaf
System.out.println("leaf: " + s); // leaf 이다. 단어가 하나 완성되었다.
}
}
static Node root = new Node();
public static void main(String[] args) {
String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
for (String word : words) {
root.add(word, 0);
}
root.print("");
}
}
leaf: frame
중간: fram 1
중간: fra 1
leaf: frodo
중간: frod 1
leaf: front
중간: fron 1
leaf: frost
중간: fros 1
leaf: frozen
중간: froze 1
중간: froz 1
중간: fro 4
중간: fr 5
중간: f 5
leaf: kakao
중간: kaka 1
중간: kak 1
중간: ka 1
중간: k 1
중간: 6
추가적으로 필드에 count를 추가하여 해당 노드에 단어의 개수를 저장하였다.
public class SearchLyrics_trie_3 {
static class Node {
int count;
Node[] nodes;
public void add(String word, int index) {
++count;
if (index == word.length()) return; // index 가 범위를 벗어났다.
if (nodes == null) nodes = new Node[26]; // 알파벳 숫자 만큼 자식 노드를 만든다.
int c = word.charAt(index) - 'a'; // word 에서 index 위치 문자가 'a' 이면 0 번째
// 'b' 이면 1 번째, 'c' 이면 2 번째 자식 노드이어야 한다.
if (nodes[c] == null) nodes[c] = new Node();
nodes[c].add(word, index + 1);
}
public void print(String s) {
if (nodes != null) { // 아직 leaf 노드가 아니다.
for (int i = 0; i < nodes.length; i++) // 자식 노드 재귀 호출 해야 한다.
if (nodes[i] != null)
nodes[i].print(s + (char)('a' + i)); // 현재 노드의 문자를 더해서, 자식 노드 재귀호출
System.out.printf("중간: %s %d\n", s, count); // 중간노드의 자식 leaf 의 수 출력
} else // leaf
System.out.println("leaf: " + s); // leaf 이다. 단어가 하나 완성되었다.
}
}
static Node[] roots = new Node[10000]; // 최대 단어 길이 10000, index 범위는 0 ~ 9999
// 단어 길이 마다 trie 트리를 따로 만든다.
static void add(String word) {
int i = word.length() - 1; // 단어 길이 -1을 index 로 한다 (0 ~ 9999)
if (roots[i] == null) roots[i] = new Node(); // 그 위치에 trie 루트 노드가 없다면 만든다.
roots[i].add(word, 0);
}
static void print() {
for (Node root : roots)
if (root != null) root.print("");
}
public static void main(String[] args) {
String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
for (String word : words) {
add(word);
}
print();
}
}
leaf: frame
중간: fram 1
중간: fra 1
leaf: frodo
중간: frod 1
leaf: front
중간: fron 1
leaf: frost
중간: fros 1
중간: fro 3
중간: fr 4
중간: f 4
leaf: kakao
중간: kaka 1
중간: kak 1
중간: ka 1
중간: k 1
중간: 5
leaf: frozen
중간: froze 1
중간: froz 1
중간: fro 1
중간: fr 1
중간: f 1
중간: 1
검색 시간을 줄이기 위해 단어의 길이별로 trie 트리를 생성하였다.
import java.util.Arrays;
public class SearchLyrics_trie_4 {
static class Solution {
static class Node {
int count = 0;
Node[] nodes = null;
public void add(String word, int index) {
++count;
if (index == word.length()) return;
if (nodes == null) nodes = new Node[26];
int j = word.charAt(index) - 'a';
if (nodes[j] == null) nodes[j] = new Node();
nodes[j].add(word, index + 1);
}
public int count(String query, int index) {
if (nodes == null) return count;
char ch = query.charAt(index);
if (ch == '?') return count;
Node node = nodes[ch - 'a'];
if (node == null) return 0;
return node.count(query, index + 1);
}
}
Node[] roots1 = new Node[10000], roots2 = new Node[10000];
String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}
void createTree(String[] words) {
for (String word : words) {
int i = word.length() - 1;
if (roots1[i] == null) roots1[i] = new Node();
if (roots2[i] == null) roots2[i] = new Node();
roots1[i].add(word, 0);
roots2[i].add(reverse(word), 0);
}
}
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
createTree(words);
for (int i = 0; i < queries.length; i++) {
String query = queries[i];
int j = query.length() - 1;
if (roots1[j] == null) continue;
if (query.charAt(0) != '?')
answer[i] = roots1[j].count(query, 0);
else
answer[i] = roots2[j].count(reverse(query), 0);
}
return answer;
}
}
public static void main(String[] args) {
String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
String[] queries = {"fro??", "????o", "fr???", "fro???", "pro?", "?????"};
System.out.println(Arrays.toString(new SearchLyrics_1.Solution().solution(words, queries)));
}
}
[3, 2, 4, 1, 0, 5]
?가 앞에서 부터 시작하게 되면 trie를 사용하는데 제약이 생기기 때문에 탐색할 때 뒤짚어준다.
references.
소프트웨어공학과 이승진 교수님의 특강자료를 기반으로 작성된 게시글입니다.