골드에그

1. 문제요약

코딩테스트 연습 - 가사 검색 | 프로그래머스 스쿨 (programmers.co.kr)

가사에 사용된 단어들이 담긴 배열 words 와 찾고자 하는 키워드가 담긴 배열 queries 가 주어질 때, 각 키워드 별로 매칭된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성하라.

룰은 다음과 같다.

① 검색 키워드(queries)는 와일드카드 문자인 '?' 가 하나 이상 포함되어 있으며, '?' 는 각 검색 키워드의 접두사 아니면 접미사 중 하나로 표현될 수 있다. 중간에도 '?' 가 들어갈 수 없다. 예를 들어 "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음), "frodo"('?'가 없음) 쿼리들은 불가능하다.

② 검색 키워드(queries)는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있다.

③ 검색 키워드는 중복이 될 수 있다.

2. 문제예제

3. 팩트추출

Fact 1 : 문제 지문에 따르면, 문자열들의 최대 갯수는 100,000 개이고, 쿼리 최대 갯수는 100,000 개로 총

100,000 * 100,000 번 탐색해야 되기 때문에 단순 탐색 시 시간 초과가 발생할 수 밖에 없다. 새로운 알고리즘이 필요하다.

Fact 2 : "?" 는 중간에 있을 수 없다. 무조건 접두사나 접미사에 존재한다. 그런데 ? 의 갯수가 미정이다.
트라이를 통해 검색을 한다고 하더라도 어느 깊이까지 탐색해야 하는지 알 수 없다. 따라서 문자열을 트라이에 저장할 때, 문자열의 길이를 키로 하는 Map 에 같은 키를 가지고 있는 문자열이 몇 개인지 저장할 필요가 있다. ? 를 만났을 때 일일히 트라이의 26개 노드들을 bfs 처럼 탐색할 필요없이 그 문자열의 길이를 Map 에서 검색해서 바로 꺼낸다.

Fact 3 : 자바의 compareTo 메서드는 특이점을 가지고 있다. A.compareTo(B) 라고 가정할 때,

1) A 와 B 가 숫자라면 아래 표와 같이 명확하다.

2) A 와 B 가 문자열이라면 조금 복잡하다.

(compareTo 메서드는 문자열을 처음부터 비교하기 시작한다.)

예제들을 나열해보면 아래와 같다.

"abcd"(4) - "ab"(2) = 2, "abcd"(4) - "a"(1) = 3, "abcd"(4) - ""(0) = 4,

"abhg"(a=97) - "h"(h=104) = -7, "abcd"(c= 99) - "abfd"(f=102) = -3, "abcd"(a=97) - "c"(c=99) = -2

만약 문자열이 정렬이 되어 있는 상태에서 쿼리들을 compareTo 메서드로 비교할 때 쿼리가 크다면 음수가 나올 것이고, 쿼리가 작다면 양수가 나올 것이다.

4. 문제전략

words 문자열들을 여러 번 탐색하기 때문에 (쿼리 문제는 다 그런 듯...) words 문자열들을 정렬할 필요가 있다.

정렬하는 이유는 역시 탐색 범위를 줄이기 위해서다. 문자열을 빠르게 탐색하기 위해서는 트라이 자료구조와 이분 탐색을 생각할 수 있다.

Solving Strategy Item 1 :

처음부터 '?' 문자를 만나면 알파벳 26 가지 경우의 수를 모두 탐색해야 한다. 그래서 문자열을 뒤집어 자료구조를 준비해둔다면, 빠르게 탐색할 수 있다. ? 이 맨 마지막에 있다면 없는 경우의 수는 없고 갯수만 파악하면 되니깐 말이다.

Solving Strategy Item 2 (트라이) :

트라이 자료구조를 통해 링크드 리스트처럼 문자열들을 O(M) (여기서 M은 문자열의 길이) 복잡도로 탐색한다. 주의할 점은 트라이 자료구조를 사용한다고 하더라도 '?' 를 만나면 그 다음 문자 26 가지 알파벳들을 모두 탐색해야 하므로 비효율적이다. '?' 는 중간에는 사용하지 못 한다는 특징을 이용하여 트라이 자료구조를 '?' 전까지만 탐색하고 '?' 를 만나면 더 이상 트라이를 탐색할 필요없이 문자열의 길이를 가진 또 다른 문자열이 있는지 파악하고 그 갯수를 리턴하면 된다. 그래서 트라이 자료구조와 함께 문자열의 길이를 키로 가지고 갯수를 값으로 가지는 Map 자료구조를 같이 셋팅한다.

Solving Strategy Item 3 (이분탐색) :

트라이 자료구조를 사용할 필요없이 문자열을 정렬해놓고 정렬된 특징을 이용하여 이분탐색으로 풀이할 수도 있다. Fact 3 에서 소개한 자바의 compareTo 메서드를 사용하면 쿼리가 크다면 음수가 나오고, 쿼리가 작다면 양수가 나오기 때문에 일정한 값 분포도에 따라 이분탐색이 가능하다. ? 문자열을 빈 문자열로 치환한다면 쿼리가 적용되는 가장 낮은 위치를 가지고 올 수 있고, ? 문자열을 가장 큰 문자 값으로 치환하면 쿼리가 적용되는 가장 높은 위치를 가지고 올 수 있다. 그 위치들을 서로 빼준다면 갯수를 구할 수 있게 된다.

5. 소스코드

1) 트라이

import java.util.*;
class Solution {
    static class Trie {
        Map<Integer, Integer> lengthMap = new HashMap<>();
        Trie[] child = new Trie[26];
        void insert(String str) {
            Trie node = this;
            int len = str.length();
            lengthMap.put(len, lengthMap.getOrDefault(len, 0) + 1);
            for (char ch : str.toCharArray()) {
                int idx = ch - 'a';
                if (node.child[idx] == null)
                    node.child[idx] = new Trie();
                node = node.child[idx];
                node.lengthMap.put(len, node.lengthMap.getOrDefault(len, 0) + 1);
            }
        }
        int find(String str, int i) {
            if (str.charAt(i) == '?')
                return lengthMap.getOrDefault(str.length(), 0);
            int idx = str.charAt(i) - 'a';
            return child[idx] == null ? 0 : child[idx].find(str, i + 1);
        }
    }
    public static int[] solution(String[] words, String[] queries) {
        Trie front = new Trie();
        Trie back = new Trie();
        for (String word : words) {
            front.insert(word);
            back.insert(reverse(word));
        }
        return Arrays.stream(queries).mapToInt(
                query -> query.charAt(0) == '?' ?
                        back.find(reverse(query), 0) :
                        front.find(query, 0)).toArray();
    }
    private static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

2) 이분탐색

import java.util.*;

class Solution {
    public static List<Integer> solution(String[] words, String[] queries) {
        Map<Integer, List<String>> frontMap = new HashMap<>();
        Map<Integer, List<String>> backMap = new HashMap<>();

        // words 리스트를 자료구조에 셋팅한다.
        for (String word : words) {
            int len = word.length();
            frontMap.computeIfAbsent(len, i -> new ArrayList<>()).add(word);
            backMap.computeIfAbsent(len, i -> new ArrayList<>()).add(reverse(word));
        }

        for (int key : frontMap.keySet()) {
            frontMap.get(key).sort(null);
            backMap.get(key).sort(null);
        }

        List<Integer> result = new ArrayList<>();
        for (String query : queries) {
            List<String> list;
            if (query.charAt(0) == '?') {
                list = backMap.get(query.length());
                query = reverse(query);
            } else
                list = frontMap.get(query.length());
            if (list == null) result.add(0);
            else result.add(lowerBound(list, query.replace('?', Character.MAX_VALUE))
                    - lowerBound(list, query.replace("?", "")));
        }
        return result;
    }
    private static int lowerBound(List<String> list, String str) {
        int start = 0, end = list.size();
        while (start < end) {
            int mid = (start + end) / 2;
            if (str.compareTo(list.get(mid)) <= 0)
                end = mid;
            else start = mid + 1;
        }
        return start;
    }
    private static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}