[프로그래머스] 캐시(C++)

[문제]

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

코딩테스트 연습 - [1차] 캐시

[풀이]

LRU 알고리즘으로 캐시를 관리하며, 캐시에서 읽어올 경우 +1, 캐시에 존재하지 않는 데이터일 경우 +5를 추가하여 총 실행시간을 구하는 문제이다. 

LRU란 Least Recently Used로 새로운 데이터가 들어올 경우, 가장 오랫동안 참고하지 않은 데이터를 빼고 새로운 데이터를 삽입하는 방식이다.

따라서 각 데이터에 대해 이미 캐시에 데이터가 존재하는지 확인 후 , 존재하지 않는다면 캐시에 삽입하고 +5를 해준다.

존재할 경우 가장 최신에 조회한 데이터이므로 벡터의 맨 뒤로 넣어주고 +1을 하여 총 실행시간을 구할 수 있다.

 

[코드]

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

using namespace std;

vector <string> v;

string solve(string tmp)
{
    string res = "";
    for(int i=0;i<tmp.size();i++){
        if(tmp[i] >= 97 && tmp[i] <= 122)   res += (tmp[i] - 32);
        else res += tmp[i];
    }
    return res;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    for(int i=0;i<cities.size();i++){
        string city = solve(cities[i]);
        if(cacheSize == 0) {
            answer+=5;
            continue;
        }
        auto itr = find(v.begin(),v.end(), city);
        if( itr != v.end()) {
            answer += 1;
            v.erase(itr);
        }  
        else{
            if(v.size() == cacheSize){
                v.erase(v.begin());
            }
            answer += 5;
        }
        v.push_back(city);
    }
    return answer;
}