캐시

코드

[ 나의 풀이 ]

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
//17 07시작
using namespace std;
/* vector<pair<string,int>> 에서 특정 값을 찾기 위한 함수 & 전역변수 */
string fstr = "";
bool findValue(pair<string, int> a){
    if(a.first == fstr) return true;
    return false;
}
/* vector<pair<string,int>> 에서 minValue찾기 위한 함수 */
bool findMIN(pair<string, int> a, pair<string, int> b){
    if(a.second < b.second) return true;
    return false; // false 처리 안하면 에러뜸
}
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<pair<string,int>> cache;
    pair<string,int> LRUpair;
    /* 캐시 사이즈가 0일때 - 예외처리 */
    if(cacheSize ==0)  return cities.size() * 5;
    /* 문자를 모두 소문자로 변경 */
    for(int i=0;i<cities.size();i++)
        for(int j=0;j<cities[i].length();j++) cities[i][j] = tolower(cities[i][j]);
    LRUpair = {cities[0],0};
    for(int i=0;i<cities.size();i++)
    {
        /* 해당 값이 cache에 있는지 파악 */
        fstr = cities[i];
        auto it = find_if(cache.begin(), cache.end(), findValue);
        if(it == cache.end()){
            answer += 5;
            /* 값이 없을 때, cache에 자리가 있으면 삽입 */
            if(cache.size() != cacheSize) {
                cache.push_back({fstr, i});
                // 삽입할 때도 LRU 업데이트가 필요할 수 있음
                if(LRUpair.first == fstr){
                    int midx = min_element(cache.begin(), cache.end(), findMIN) - cache.begin();
                    LRUpair = {cache[midx].first, cache[midx].second};
                }
            }
            /* 값이 없을 때, cache에 자리가 없으니 LRU에 실행 */
            else{
                fstr = LRUpair.first;
                int idx= find_if(cache.begin(), cache.end(), findValue) - cache.begin();
                cache[idx] = {cities[i], i};
                /* LRUpair을 update! */
                int midx = min_element(cache.begin(), cache.end(), findMIN) - cache.begin();
                LRUpair = {cache[midx].first, cache[midx].second};
            }
        }else{
            answer += 1;
            int idx = find_if(cache.begin(), cache.end(), findValue) - cache.begin();
            cache[idx] = {fstr, i};
            /* LRUpair을 update! */
            if(LRUpair.first == fstr){
                int midx = min_element(cache.begin(), cache.end(), findMIN) - cache.begin();
                LRUpair = {cache[midx].first, cache[midx].second};
            }
        }
    }
    return answer;
}

• 캐시(cache) 공간을 vector<pair<string,int>> 자료형으로 만들었음
  --> string은 지역 이름, int는 LRU 수행하기 위한 최근 들어간 idx값

• LRU 수행 로직 (LRUpair은 다음에 빠져야 할 pair!)
  1) cache에 해당 값이 없으며, cache가 가득차지 않았을 때 (cache에 삽입)
  : 지금 LRUpair인 문자열을 또 입력할 수 있으니, 같은 경우 갱신해줘야함

  2) cache에 해당 값이 없지만, 가득 차있을 때 (cache 값 변경)
  : LRUpair이 있던 index를 구해서, cache에 현재 들어온 값을 삽입!
    이후에, 새로운 LRUpair를 구할 때에는 cache에서 최근 들어간 idx가 제일 작은 값을 찾아온다!

  3) cache에 해당 값이 있을 때 (cache 값 갱신)
  : 이미 있는 값이기 때문에, 최근 index로 갱신

---

[ 깨달음 ]

1) vector<pair<string, int>> v 에서 값(int)이 최소인 인덱스 찾기

bool findMIN(pair<string, int> a, pair<string, int> b){
    if(a.second < b.second) return true;
    return false; 
}
vector<pair<string,int>> cache;
int midx = min_element(cache.begin(), cache.end(), findMIN) - cache.begin();

2) vector<pair<string, int>> v 에서 특정 요소(int)값인 인덱스를 찾기

string fstr = "";
bool findValue(pair<string, int> a){
    if(a.first == fstr) return true;
    return false;
}
vector<pair<string,int>> cache;
auto it = find_if(cache.begin(), cache.end(), findValue); // iterator찾기
int idx = find_if(cache.begin(), cache.end(), findValue) - cache.begin(); // 인덱스찾기

• 값은 전역변수를 이용해야 하는게 조금 귀찮지만 가능한게 다행
• find_if를 기억하자

3) <algorithm>의 transform() : 해당 범위에 있는 요소에 해당 함수를 반복해 적용

    vector<string> v;
    v.push_back("abc");
    v.push_back("def");
    v.push_back("ghi");
    for(auto it = v.begin();it != v.end();it++)
        transform(it->begin(), it->end(), it->begin(), ::toupper);
        // ABC
        // DEF
        // GHI

• 여러개의 문자열들을 한번에 대/소문자로 바꾸기에 매우 적합하고 신기함~

---

[ 다른 풀이 ] - 최적

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

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;
    /* cache크기가 0일때 - 예외처리 */
    if(cacheSize == 0) return 5*cities.size();
    /* 모든 요소를 소문자로 바꾸기 */
    for(auto it = cities.begin();it != cities.end();it++)
        transform(it->begin(), it->end(), it->begin(), ::tolower);
    for(int i=0;i<cities.size();i++)
    {
        string str = cities[i];
        auto it = find(cache.begin(), cache.end(), str);
        /* 해당 값이 cache에 있으면 */
        if(it != cache.end()){
            answer += 1;
            cache.erase(it);
            cache.push_back(str);
        }else{
            /* 해당 값이 cache에 없으면 */
            answer += 5;
            if(cache.size() == cacheSize) cache.erase(cache.begin());
            cache.push_back(str);
        }
    }
    return answer;
}

• LRU를 매우 간단하게 해결해서 코드가 짧아진 것같다.
• cache에 순서대로 집어 넣되, 원래 값이 있으면 삭제하고 뒤로 다시 넣는 것이 keypoint!
• string 클래스의 erase는 매개변수가 2개 / 다른 container에서는 매개변수 1개 (iterator) 필요!