[2020 KAKAO BLIND RECRUITMENT] 가사 검색

코딩테스트 연습 - 가사 검색

 정확성과 효율성 테스트 각각 점수가 있는 문제이다.

 

가사 단어의 제한사항

 - 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
kakao

---

 trie가 잘 만들어 진것을 확인 할 수 있다.

 

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.

소프트웨어공학과 이승진 교수님의 특강자료를 기반으로 작성된 게시글입니다.