642. Design Search Autocomplete System

문제: leetcode.com/problems/design-search-autocomplete-system/

 검색 시에 매칭되는 문자열들을 자동으로 완성시켜주는 알고리즘 구현이다.  검색창에서 특정 문자를 치면 해당 문자를 prefix로 포함한 문자열들을 나열해주는 것과 같다.  

 처음에 몇 번 입력했었다는 조건이 주어지며, 문자열을 검색할 때마다 카운트가 증가되는 것을 반영해주면 된다.

입력 반영 키포인트

 한 문자를 입력할 때마다 출력해야한다.  예시에서 보면 "I love you"라는 문자열을 추가적으로 입력했다.  이후에는 "I love you"라는 문자열의 times가 5에서 6으로 증가하며 이를 반영해서 문자열 추천을 해줘야한다.

 

class AutocompleteSystem {
public:
    priority_queue<pair<int, string>> pq;
    int pos = 0;
    string s = "";
    
    unordered_map<string, int> m;
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        for(int i = 0; i < sentences.size(); i++){
            m[sentences[i]] = times[i];
            pq.push(make_pair(times[i], sentences[i]));
        }
    }
    
    void reverse(vector<pair<int, string>>& ts, int i, int j){
        while(i < j){
            pair<int, string> tmp = ts[i];
            ts[i] = ts[j];
            ts[j] = tmp;
            i++;
            j--;
        }
    }
    
    vector<string> input(char c) {
        vector<string> ret;
        if(c == '#'){
            pos = 0;
            m[s]++;
            s = "";
            while(!pq.empty()) pq.pop();
            for(auto v : m){
                pq.push(make_pair(v.second, v.first));
            }
            return ret;
        }
        s += c;
        
        vector<pair<int, string>> saved;
        
        while(!pq.empty()){
            pair<int, string> ts = pq.top();
            pq.pop();
            int time = ts.first;
            string sentence = ts.second;
            
            if(pos < sentence.size() && c == sentence[pos]){
                saved.push_back(ts);
            }
        }
        
        int left = 0, right = 0;
        
        while(right < saved.size()){
            while(right+1 < saved.size() && saved[left].first == saved[right + 1].first){
                right++;
            }
            reverse(saved, left, right);
            right++;
            left = right;
        }
        
        
        
        for(int i = 0; i < saved.size(); i++){
            if(ret.size() < 3){
                ret.push_back(saved[i].second);
            }
            pq.push(saved[i]);
        }
        pos++;
        return ret;
    }
};

/**
 * Your AutocompleteSystem object will be instantiated and called as such:
 * AutocompleteSystem* obj = new AutocompleteSystem(sentences, times);
 * vector<string> param_1 = obj->input(c);
 */

 pq를 사용하고 최대값 순으로 times를 꺼내는데 setence에서는 아스키값이 작은 순으로 정렬해야해서 linear search하면서 해당 구간만 reverse 해줬다.  

 

 속도가 무지하게 느린데... 최적화 방법을 추가적으로 생각해봐야겠다.