[프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT - JAVA

🔗 문제 링크

[프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT

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

 

1️⃣ Trie

📝 풀이 과정

words의 길이는 100,000개, queries의 길이는 100,000개로 단순 탐색시 시간 초과가 발생한다.

 

다음으로 생각한 풀이는 Trie를 사용하는 방법이었다.

 

words를 모두 Trie에 insert한 다음 queries를 통해 문자열을 검색할 때, 삽입된 문자열의 길이를 모른다면 탐색하기 어렵다. 때문에, Trie의 노드마다 lenMap을 생성하였다. key는 삽입된 문자열의 길이고, value는 해당 길이의 문자열의 개수를 가지고 있다. 따라서 Trie의 node 위치에 도달했을 때, 해당 노드까지 도달할 수 있는 문자열의 수를 구할 수 있게 된다.

 

또한, 문제에서 쿼리는 앞과 뒤에서 '?'(와일드 카드)가 존재하는 경우가 주어진다(중간에 들어가는 경우는 없다). 따라서 뒤집힌 문자열로 구성된 Trie도 생성해야 한다.

front
tnorf

 

탐색할 때 제일 앞의 문자가 '?'가 아니라면 기본 Trie를 통해 탐색한 값을 반환하고, 아니라면 뒤집힌 문자열로 구성된 Trie를 탐색한 결과를 반환한다.

 

💻 코드

import java.util.*;

class Solution {
    class Trie {
        Map<Integer, Integer> lenMap = new HashMap<>();
        Trie[] child = new Trie[26];

        void insert(String str) {
            Trie node = this;
            int len = str.length();
            lenMap.put(len, lenMap.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.lenMap.put(len, node.lenMap.getOrDefault(len, 0) + 1);
            }
        }

        int find(String str, int i) {
            if (str.charAt(i) == '?')
                return lenMap.getOrDefault(str.length(), 0);

            int idx = str.charAt(i) - 'a';
            return child[idx] == null ? 0 : child[idx].find(str, i + 1);
        }

    }

    public 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();
    }
    
    String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

 

---

 

2️⃣ 이분탐색

📝 풀이 과정

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설을 보면서 이분탐색을 통한 풀이도 가능하다고 알게 되어 다시 풀어보았다.

 

이번에는 이분탐색을 사용하기 위해 List를 사용하였다. 길이에 따라 맵을 다르게 생성해주기 위해 Map을 사용하였다. key는 문자열의 길이고, value는 해당 길이의 문자열들의 List이다. Trie로 구현할 때와 같이 뒤집힌 문자열로 이루어진 List도 만들어주었다.

만약, List가 생성되지 않았을 경우 computeIfAbsent()를 사용해 List를 생성하고 문자열을 추가하였다.

 

다음으로 쿼리에 해당하는 문자열들의 개수를 찾기위해 이분탐색을 했다. String의 compareTo() 메소드는 하나씩 비교하다가 다른 문자가 나올 때 작은 값, 길이가 짧은 순으로 정렬된다.

따라서, 쿼리의 와일드카드를 제외하고 lower_bound를 구해주면 쿼리가 적용되는 가장 낮은 위치가 된다. 반대로 쿼리의 와일드카드를 Character.MAX_VALUE로 변경하고 lower_bound를 찾으면 쿼리가 적용되는 제일 높은 위치를 구할 수 있기 때문에 둘의 차를 구하면 적용되는 단어 수를 구할 수 있기 된다.

 

💻 코드

import java.util.*;

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

        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> ans = 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) ans.add(0);
            else ans.add(lowerBound(list, query.replace('?', Character.MAX_VALUE))
                    - lowerBound(list, query.replace("?", "")));
        }

        return ans;
    }

    int lowerBound(List<String> list, String str) {
        int s = 0, e = list.size();

        while (s < e) {
            int m = (s + e) / 2;

            if (str.compareTo(list.get(m)) <= 0)
                e = m;
            else s = m + 1;
        }

        return s;
    }

    String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}