알고리즘) 카카오 블라인드 채용 2020, 가사 검색

Kakao Blind Recruitment 2020

가사 검색

프로그래머스

 

주목해야할 조건

검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.

풀이

처음 문제를 보고 어? 쉽네? 라고 접근했다. 선형 loop를 통해 조건에 맞는지 확인하고 count를 업데이트 하는 식으로 짰다. 하지만, 역시나 카카오는 쉬울리가 없다.. 효율성에서 1,2,3번이 틀렸다. 여기서 '아.. Trie구나' 라고 생각했다. Trie를 떠올린 것 까지는 좋았지만, 역시나 시간초과가 떴다. 검색을 통해 역방향 트라이를 만들면 된다는 글의 도움을 받아 다시 코드를 짰다. 하지만, 효율성 3번 문제가 틀리는 것이었다. query가 ?로만 이루어진 경우를 생각하여 추가해서 통과했다.

 

1. 정방향, 역방향 트리를 만든다.

2. Query의 첫 글자가 ?인지 아닌지 확인하여, 정방향 / 역방향 트리에서 찾아준다.

3. 만약 Query의 모든 글자가 ?이면, ? 길이 만큼의 문자가 존재하는지 여부를 확인한다.

 3-1. ?길이 만큼 존재한다면, 그 길이에 해당하는 Count를 리턴한다. 예를 들어 Query가 "?????" 라면, 5글자인 word가 존재하는 만큼 개수를 리턴한다.

 3-2. 만약, ?길이에 해당하는 word가 없으면 0을 리턴한다.

 

코드 1

package kakao;

public class SearchLyrics {
    private static int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        
        for(int i=0; i<answer.length; i++) {
            answer[i] = getCount(words, queries[i]);
        }

        return answer;
    }

    private static int getCount(String[] words, String query) {
        int cnt =0;

        for(String word : words) {
            if(rightWord(word, query)) {
                cnt++;
            }
        }
        return cnt;
    }

    private static boolean rightWord(String word, String query) {
        if(word.length() != query.length()) {   // 길이가 다르면 X
            return false;
        }
        for(int idx =0; idx < word.length(); idx++) {
            if(query.charAt(idx) != '?') {
                if(word.charAt(idx) != query.charAt(idx)) { // 다른 글자면 break;
                    return false;
                }
            }
        }
        return true;
    }


    public static void main(String[] args) {
        String[] words ={"frodo", "front", "frost", "frozen", "frame", "kakao"};
        String[] queries ={"fro??", "????o", "fr???", "fro???", "pro?"};
        int[] result = solution(words, queries);

        for(int num : result) {
            System.out.println(num);
        }
    }
}

 

코드 2

package kakao;

import java.util.HashMap;

public class SearchLyrics {
    private static int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        Trie trie = getTrie(words); // 정방향 Trie
        Trie reverseTrie = getReverseTrie(words);   // 역방향 Trie

        for(int i=0; i<answer.length; i++) {
            answer[i] = getCount(trie, reverseTrie, queries[i]);
        }

        return answer;
    }

    private static int getCount(Trie trie, Trie reverseTrie, String query) {    // query 에 해당하는 문자열 cnt 반환
        int cnt =0;
        if(query.charAt(0) == '?') {    // reverse 트리에서 탐색
            StringBuffer sb = new StringBuffer(query);
            cnt += reverseTrie.search(sb.reverse().toString());
        } else {    // trie 탐색
            cnt+= trie.search(query);
        }
        return cnt;
    }

    private static Trie getTrie(String[] words) {   // 정방향 트리 초기화 및 반환
        Trie trie = new Trie();
        for(String word : words) {
            trie.insert(word);
        }
        return trie;
    }

    private static Trie getReverseTrie(String[] words) {    // 역방향 트리 초기화 및 반환
        Trie trie = new Trie();
        for(String word : words) {
            StringBuffer sb = new StringBuffer(word);
            trie.insert(sb.reverse().toString());
        }
        return trie;
    }

    public static void main(String[] args) {
        String[] words ={"frodo", "front", "frost", "frozen", "frame", "kakao"};
        String[] queries ={"fro??", "????o", "fr???", "fro???", "pro?"};
        int[] result = solution(words, queries);

        for(int num : result) {
            System.out.println(num);
        }
    }
}

class Node {    // Node class
    char ch;
    HashMap<Character, Node> children;          // 자식 노드
    HashMap<Integer, Integer> childrenCnt;      // 와일드카드 ?를 위해, key에는 query의 길이, value에는 갯수가 들어감
    boolean isEnd;                              // 끝인지 판별하는 boolean 이지만 여기서는 필요 없을 것 같기도

    public Node() {
        this.children = new HashMap<>();
        this.childrenCnt = new HashMap<>();
    }
    public Node(char ch) {
        this.children = new HashMap<>();
        this.childrenCnt = new HashMap<>();
        this.ch = ch;
    }
}

class Trie {
    private Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {   // word 삽입
        HashMap<Character, Node> children = root.children;
        updateChildrenCnt(root, word.length()); // query 의 모든 글자가 ? 로 이루어진 경우를 위해, root에도 저장

        for(int i=0; i<word.length(); i++) {
            char ch = word.charAt(i);
            Node tmp;
            if(children.containsKey(ch)) {  //이미 있으면, 들어가기
                tmp = children.get(ch);
                children = tmp.children;
            } else {    // 없으면 만들어서 삽입 후, children 으로 들어감
                tmp = new Node(ch);
                children.put(ch, tmp);
                children = tmp.children;
            }
            updateChildrenCnt(tmp, word.length());  //  각 depth 마다 word(query)의 length 만큼 가진 갯수 저장
            if(i == word.length()-1) {
                tmp.isEnd = true;
            }
        }
    }
    public void updateChildrenCnt(Node node, int len) { // length 갯수 저장
        if(node.childrenCnt.containsKey(len)) {
            node.childrenCnt.replace(len, node.childrenCnt.get(len)+1);
        } else {
            node.childrenCnt.put(len, 1);
        }
    }

    public int search(String word) {
        if(word.replaceAll("[?]","").length() ==0) {    // 모든 문자가 ?로 이루어진 경우
            if(root.childrenCnt.containsKey(word.length())) {   // 글자 수 만큼 있으면
                return root.childrenCnt.get((word.length()));   // 갯수 반환
            } else {    // 없으면
                return 0;   //0 반환
            }
        }
        HashMap<Character, Node> children = root.children;
        Node tmp = null;

        int cnt = 0;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (ch != '?') {    // ?가 아닌 경우
                if (children.containsKey(ch)) {  // ch가 있으면
                    tmp = children.get(ch);     // 들어가자
                    children = tmp.children;
                } else {    // 다른 글자면
                    return 0;   // 맞는 조건 없음
                }
            } else {    // ?를 만났으면
                if (tmp.childrenCnt.containsKey(word.length())) {   // query 의 갯수 만큼 존재하는 cnt 반환
                    cnt = tmp.childrenCnt.get(word.length());
                    break;
                }
            }
        }
        return cnt;
    }
}