가사 검색

프로그래머스 가사 검색 풀이

문제설명

친구들로부터 천재 프로그래머로 불리는 “프로도”는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.

그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 ‘?’가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 ‘?’는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

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

제한사항

• 가사단어 개수, 쿼리 개수 ≤ 100,000
• 각 단어와 쿼리의 길이 ≤ 10,000

해결과정

가사 단어의 개수가 $10^5$이라, unordered_map으로 해결하는 것을 생각했다. $O(10^5 * 10^4)$ 으로 map을 채우면 쿼리는 시간복잡도는 이론상 O(1)이다. 하지만, 효율성테스트에서 2개의 tc에서 시간초과가 발생한다. 아마 map의 사이즈가 커지면서, map에 삽입하는 연산의 걸리는 시간이 더 크게 나온모양이다.

소스코드

#include <bits/stdc++.h>
using namespace std;
// 10^5 * 10^5
unordered_map<string, int> mmap[10001];
unordered_map<int, int> all;
vector<int> solution(vector<string> words, vector<string> queries) {
    for(const string& word : words){ 
        int ssize = word.size();
        all[ssize]++;
        string a = word;
        string b = word;
        for(int i = 0; i < ssize; i++){
            a[i] = '?';
            b[ssize - i - 1] = '?';
            mmap[ssize][a]++;
            mmap[ssize][b]++;
        }
    
    }
    vector<int> ans;
    int q_size = queries.size();
    ans.resize(q_size);
    for(int i = 0; i<q_size; i++){
        int cur_size = queries[i].size();
        if(queries[i].front() == '?' && queries[i].back() == '?') ans[i] = all[q_size];
        else ans[i] = mmap[cur_size][queries[i]];
    }
    return ans;
    
}

배운점

아직 트라이에 대해, 완전히 익숙하지 않아서 트라이로 구현하길 꺼렸는데 빨리 트라이를 학습해야겠다.