'Programming Problems/Hashing'에 해당되는 글 2건

Programming Problems/Hashing

URL 배열 중에서 중복되지 않은 첫 원소 찾기

제곧내


해시 테이블에 "반복되지 않은" 원소들을 넣는다. 즉, 처음 만난 원소면 넣고, 리스트에 append하고 그 포인터를 맵에 저장한다.

만약 반복되면 그 리스트 포인터를 지우고 포인터를 널로 만든다. 이미 널이면 이미 두번 이상 나왔다는 거니까 무시한다.


string findfirstuniqueURL(vector<string> & data){

// make buffer elements

list<string> tmp;

unordered_map<string,list<string>::iterator> buffer;

// go through data

for(int i = 0 ; i  < data.size() ; i++){

auto it = buffer.find(data[i]);

if(it!=buffer.end()){

if(it->second!=NULL){

tmp.erase(it->second);

it->second==NULL;

}

}else{

list.push_back(data[i]);

buffer.insert(pair<string,list<string>::iterator>(data[i],--list.end()));

}

}

// return first element in list

return list.front();

}


time complexity : O(N)

space complexity : O(N)


OK..!!

Programming Problems/Hashing

검색기록 확인하기 ( 최근 5개 )

검색기록을 확인하는 프로그램을 작성하자. 같은 페이지를 방문하면 최근으로 다시 갱신된다.

ex ) GABCAY >> YACBG


최근 기록을 리스트로 관리한다. 해시 테이블에 현재 존재하는 값들을 저장한다.

새로운 값이 이미 존재했던 값이면 리스트 포인터를 맨 앞으로 옮긴다. 없던 값이면 리스트 끝을 드랍하고 새로운 값을 넣는다.


string recents(string & s ){

unordered_map<char,list<char>::iterator> hash;

list<char> recent;

for(int i = 0 ; i < s.size() ; i++){

if(hash,size()<5){

// append at back

recent.push_back(s[i]);

hash.insert(pair<char,list<char>::iterator>(s[i],--recent.end()));

}else{

auto it = hash.find(s[i]);

if(it!=hash.end()){

recent.erase(it->second);

recent.push_front(s[i]);

it->second = recent.begin();

}else{

// new element

hash.erase(recent.back());

recent.pop_back();

recent.push_front(s[i]);

hash.insert(pair<char,list<char>::iterator>(s[i],recent.begin());

}

}

}

// print list

string ret = "";

for(char x : recent){

ret.push_back(x);

}

return ret;

}


시간 복잡도 : O(N)