[알고리즘C++][1차]캐시

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/17680

캐시

나의 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> qu;
    
    for(int i=0;i<cities.size();i++){
        string str = cities[i];
        transform(str.begin(), str.end(), str.begin(), ::tolower);
        bool check = false;
        int idx;
        for(int j=0;j<qu.size();j++){
            if(str == qu[j]){
                check = true;
                idx = j;
            }
        }
        if(check == true){ // 있으면
            answer++; 
            qu.erase(qu.begin()+idx);
            qu.push_back(str);
        }else{ // 없으면
           answer+=5; 
            if(cacheSize != 0){
                if(qu.size() == cacheSize){
                    qu.erase(qu.begin());
                }
                qu.push_back(str);
            }
        }
    }
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int solution(int cacheSize, vector<string> cities) {

    vector <string> q;
    int duration = 0;

    for(vector <string>::iterator it = cities.begin(); it != cities.end(); it++){
        transform(it->begin(), it->end(), it->begin(), ::tolower);

        bool flag = false;
        for(vector<string>::iterator itt = q.begin(); itt != q.end(); itt++){
            if(*itt == *it) {
                flag = true;
                duration +=1;
                q.erase(itt);
                q.push_back(*it);
                break;
            }
        }
        if(!flag) {
            duration +=5;
            if(cacheSize != 0 && q.size() >= cacheSize)
                q.erase(q.begin());
            if(q.size() < cacheSize)
                q.push_back(*it);
        }
    }

    return duration;
}

배울 점

• 메모리 문제로 먼저 set과 queue로 구현해 둔것을 다 지웠다. vector하나로 구현
• 두번째 문제는 기억에 의존하여 LRU니까 가장 오래된것만 지우니까 0번째만 지우겠다 하핫^^ 하고 풀다가 hit 경우를 생각 안해버림 hit의 경우 사용된 거니까 다시 위로 올려줘야하는것을 LRU를 검색해보고 알았음. 정확이 알아보자꾸나..
• 아하 true인 경우는 저기에서 끝내면 되잖아!! 그 외에는 코드가 거의 같다