[2020카카오공채] 가사 검색

TPark·2019년 11월 27일
1

알고리즘

목록 보기
6/13

문제출처: https://programmers.co.kr/learn/courses/30/lessons/60060

문제

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

풀이

예전에 풀었던 문제인데 프로그래머스 레벨테스트에 이 문제가 나와서 다시 한번 풀어봤다. 처음 풀때에 Trie 자료구조를 생각하지 못해 애먹었던 기억이 있다. 예전에 풀었던 코드를 보니 똑같이 Trie를 사용했지만 이번에는 해당 단어 길이를 가지고 있는 자식의 수를 Node에 저장해주는 방식으로 풀었고, 전에는 DFS를 응용해서 자식의 수를 계산하는 방식으로 풀었다.
어쨌든 이 문제의 핵심 포인트는 Trie 자료 구조를 사용하는 것이고, 또 키워드가 뒤에서부터 시작할때는 거꾸로된 Trie를 따로 만들어서 검색해야 한다는게 포인트 이다.

이번 코드

class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        Trie root = new Trie('*');
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            Trie prev = root;
            for (int j = 0; j < word.length(); j++) {
                char c = word.charAt(j);
                Trie curr = new Trie(c);
                prev = prev.putChild(curr, word.length());
            }
        }
         
        for (int i = 0; i < queries.length; i++) {
            String query = queries[i];
            Trie trav = root;
            if (query.charAt(0) == '?') continue;
            for (int j = 0; j < query.length(); j++) {
                char c = query.charAt(j);
                if (c == '?') {
                    answer[i] = trav.getNumChildrenWithLen(query.length());
                    break;
                }
                trav = trav.getChild(c);
                if (trav == null) {
                    answer[i] = 0;
                    break;
                }
                
            }
        }
        
        //reverse
        Trie rootReverse = new Trie('*');
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            Trie prev = rootReverse;
            for (int j = word.length() - 1; j >= 0; j--) {
                char c = word.charAt(j);
                Trie curr = new Trie(c);
                prev = prev.putChild(curr, word.length());
            }
        }
         
        for (int i = 0; i < queries.length; i++) {
            String query = queries[i];
            Trie trav = rootReverse;
            if (query.charAt(0) != '?') continue;
            for (int j = query.length() - 1; j >= 0; j--) {
                char c = query.charAt(j);
                if (c == '?') {
                    answer[i] = trav.getNumChildrenWithLen(query.length());
                    break;
                }
                trav = trav.getChild(c);
                if (trav == null) {
                    answer[i] = 0;
                    break;
                }
            }
        }
        return answer;
    }
    
    class Trie {
        char c;
        HashMap<Character, Trie> children;
        HashMap<Integer, Integer> numChildrenWithLen;
        
        Trie(char c) {
            this.c = c;
            children = new HashMap<Character, Trie>();
            numChildrenWithLen = new HashMap<Integer, Integer>();
        }
        
        Trie putChild(Trie t, int len) {
            if (!children.containsKey(t.c)) {
                children.put(t.c, t);
            }
            if (numChildrenWithLen.containsKey(len)) {
                numChildrenWithLen.put(len, numChildrenWithLen.get(len) + 1);
            }
            else {
                numChildrenWithLen.put(len, 1);
            }
            return children.get(t.c);
        }
        
        Trie getChild(char c) {
            return children.get(c);
        }
        
        int getNumChildrenWithLen(int len) {
            if (numChildrenWithLen.containsKey(len)) return numChildrenWithLen.get(len);
            return 0;
        }
    }
}

저번 코드

class Solution {
    private final int R = 26;
    private class TrieNode {
        private TrieNode[] next;
        private boolean isEnd;
        private TrieNode() {
            next = new TrieNode[R];
        }
    }
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        TrieNode root = new TrieNode();
        TrieNode revRoot = new TrieNode();
        for (String word: words) {
            buildTrie(root, word);
            buildReverseTrie(revRoot, word);
        }
        Map<String, Integer> memo = new HashMap<>();
        for (int i = 0; i < queries.length; ++i) {
            if (memo.containsKey(queries[i])) {
                answer[i] = memo.get(queries[i]);
            } else {
                if (queries[i].charAt(0) == '?') {
                    answer[i] = lookup(revRoot, new StringBuilder(queries[i]).reverse().toString(), 0);
                } else {
                    answer[i] = lookup(root, queries[i], 0);
                }
                memo.put(queries[i], answer[i]);                
            }
        }
        return answer;
    }

    private void buildTrie(TrieNode root, String word) {
        TrieNode node = root;
        for (char c: word.toCharArray()) {
            if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
            node = node.next[c - 'a'];
        }
        node.isEnd = true;
    }
    private void buildReverseTrie(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = word.length() - 1; i >= 0; --i) {
            char c = word.charAt(i);
            if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
            node = node.next[c - 'a'];
        }
        node.isEnd = true;
    }
    private int lookup(TrieNode node, String query, int depth) {
        if (depth == query.length()) {
            if (node.isEnd) return 1;
            return 0;
        }
        char c = query.charAt(depth);
        int count = 0;
        if (c == '?') {
            for (int i = 0; i < R; ++i) {
                if (node.next[i] != null) count += lookup(node.next[i], query, depth + 1);
            }
            return count;
        } else {
            if (node.next[c - 'a'] != null) count = lookup(node.next[c - 'a'], query, depth + 1);
        }
        return count;
    }
}

Trie 외에도 정렬후 이분탐색법 등으로 풀수 있단다

0개의 댓글