99클럽 코테 스터디 12일차 TIL : 745. Prefix and Suffix Search

https://leetcode.com/problems/prefix-and-suffix-search/

 

와...진짜 수많은 삽질끝에 해쉬로 겨우풀었다......

오늘 꼭 기억할것은,,

데이터 저장할 때 미리 검색가능한 내용을 해시맵으로 저장해두는게 오히려 더 효율적일 수 있다는 점이었다!

 

생각해보면, 그냥 단어만 저장해두고 매번 검색할때마다 하나하나 찾으면

=> prefix비교, suffix비교... 이걸 검색횟수마다 매번 해야한다. 

이 때 prefix와 suffix는 string으로 주어지기 때문에 검색할 때 단어 길이만큼의 시간도 필요할것이고,, (한번에는 안끝남)

=> 이런점에서 생각했을 때 그냥 해시맵에 가능한 모든 prefix, suffix조합을 저장해두고 검색할때는 한번에 찾아주는게 훨씬 괜찮은것같다!

 

그리고 두번째 생각할점

c++ 에서 <map> 과 <unordered_map>을 적절히 사용하자!

map은 key를 기준으로 정렬을 해준다 -> 이진트리로 구현된다! 즉 삽입, 검색, 정렬,.. 등등에 logn의 시간이 소요된다

unordered_map은 그냥 해시를 이용해준다 -> 모든 동작이 상수시간만큼만 필요하다!!

=> 내가 구현하려는 내용은 순서가 크게 중요하지 않으므로, unordered를 사용해줬다

실제로 이 부분만 변경해줬는데, 러닝타임에 유의미한 차이가 있었다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <iostream>

using namespace std;



class WordFilter {
unordered_map<string, int> dics;
int dicssize = 0;
public:
    WordFilter(vector<string>& words) {
        for(int i = 0; i<words.size(); i++){
            int strsize = words[i].size();
            if(strsize == 1){
                string pref1 = words[i];
                string pref2 = words[i] +"/"+ words[i];
                dics[pref1] = dicssize;
                dics[pref2] = dicssize;
                dicssize++;
                continue;
            }
            
            for(int j = 1; j<=strsize; j++){
                string pref = words[i].substr(0, j);
                for(int k = 1; k<=strsize; k++){
                    string suff = words[i].substr(strsize-k, k);
                    dics[pref+"/"+suff] = dicssize;
                    
                }
            }
            dicssize++;
            
            
        }
    }
    
    int f(string pref, string suff) {
        string s = pref +"/" + suff;
        
        
        
        if(dics.find(s) != dics.end()){
            return dics[s];
        }
        
        return -1;
    }
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter* obj = new WordFilter(words);
 * int param_1 = obj->f(pref,suff);
 */