프로그래머스 [1차] 캐시 C++

프로그래머스 : [1차] 캐시

프로그래머스

 

---

- 문제

  LRU 캐시 교체 알고리즘을 적용하여 실행시간을 구하는 문제다.

 

---

- 풀이

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0, idx = 0;
    vector<string> s;
    for(auto city : cities){
        transform(city.begin(), city.end(), city.begin(), ::tolower);
        if(cacheSize == 0){
            answer += 5;
        }
        else if(s.size() < cacheSize && find(s.begin(),s.end(),city) == s.end()){
            s.push_back(city);
            answer += 5;
        }
        else{
            if(find(s.begin(),s.end(),city) != s.end()){
                answer += 1;
                s.erase(find(s.begin(),s.end(),city));
                s.push_back(city);
            }
            else{
                s.erase(s.begin());
                s.push_back(city);
                answer+= 5;
            }
        }
    }
    
    return answer;
}

 

 

캐시크기만큼만 도시이름을 저장해 놓고 다음 도시 이름을 읽을 때 마다 기존에 가장 Least Recently Used 도시 이름을 지우고 새로운 도시를 추가하는 방법을 이용했다.

 

  

---

- 기억할 것!

 X