[Lv 2] [1차] 캐시

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

프로그래머스

 

LRU 알고리즘을 구현하는 문제

캐시는 vector 컨테이너를 통해 구현하였다.

최근 참조된 문자열은 벡터의 가장 마지막에 위치하도록 하고 참조되지 않은 문자열은 0번째 인덱스에 위치하도록 함

따라서 캐시 미스 발생 시 캐시가 가득 찼다면 0번째 인덱스의 원소를 제거 후 벡터에 삽입하였다.

 

erase 연산 시 cahceSize가 0이면 예외가 발생하므로 0인 경우 cities.size * 5값을 반환하도록 구현

또한 대소문자 구분을 하지 않으므로 모두 소문자로 변경 후 연산 진행

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string calc(string s){
    string temp = "";
    for(int i = 0;i<s.length();i++){
        if(s[i] >= 'a' && s[i] <= 'z')
            temp += s[i];
        else
            temp += (s[i] + 32); 
    }
    return temp;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;

    if(cacheSize <= 0)
        return cities.size() * 5;
    
    for(int i = 0;i<cities.size();i++){
        string city = cities[i];
        city = calc(city);
        auto it = find(cache.begin(),cache.end(), city);
        if(it != cache.end()){ // cache hit
            cache.erase(it);
            cache.push_back(city);
            answer++;
        }
        else{ // cache miss
            // 캐시에 공간이 있을 때
            if(cache.size() < cacheSize){
                cache.push_back(city);
            }
            // 캐시에 공간이 없을 때
            else{
                cache.erase(cache.begin());
                cache.push_back(city);
            }
            answer+=5;
        }
    }
    return answer;
}