728x90
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);
*/
728x90
'코테준비 > 하루한개도전~' 카테고리의 다른 글
99클럽 코테 스터디 13일차 TIL : 모음사전 (0) | 2024.08.07 |
---|---|
8/5 TIL : 진단테스트 (0) | 2024.08.06 |
[코드트리 조별과제] : 3주차 (0) | 2024.08.04 |
8/4 TIL : DP (0) | 2024.08.04 |
99클럽 코테 스터디 11일차 TIL : 숫자 카드2 (0) | 2024.08.04 |