[ 프로그래머스 / 구현 ] 캐시 (KaKao)

1. 문제

---

 

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

 

 

2. 소스코드

---

- vector와 struct를 이용했다.

- struct에는 사용된 시간, 도시이름을 저장.

- 캐시가 비어 있으면, 현재 시간과 도시이름을 push_back하고, 비어 있지 않다면, push_back 한 뒤, push_back했다.

- 항상 캐시 맨 뒤에 있는 항목이 가장 오래된 것임을 보장하기 위해, 사용된 시간을 기준으로 매번 sort했다.

- 매번 sort를 하지않고, 항상 vector의 맨 뒤를 최근 것으로 두고, 맨 앞 원소를 삭제하는 로직을 쓸 수도 있지만 해당 방법은 매번 vector의 메모리에 재할당 해야하기 때문에 sort랑 별 차이가 없다고 생각된다. 

- 무슨 방법을 쓰든 캐시의 n이 최대 30으로 매우 작으므로 상관없다.

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
#define CACHE_HIT 1
#define CACHE_MISS 5
using namespace std;

struct Info{
    int used_time;
    string city;
};

vector<Info> cache;

bool isInCache(string cur_city, int time){
    for(int i = 0; i < cache.size(); ++i){
        if(cur_city == cache[i].city){
            cache[i].used_time = time;
            return true;
        }
    }
    return false;
}

bool compare(Info &a, Info &b) {
  return a.used_time > b.used_time;
}


int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    cache.reserve(cacheSize);
    int size = cities.size();
    if(!cacheSize) return size * 5;
    
    for(int time = 0; time < size; ++time){
        string cur_city = cities[time];
        for(int i = 0 ; i < cur_city.size(); ++i)
            cur_city[i] = tolower(cur_city[i]);
            // 1) cities[i] 캐쉬에 있는가?
            if(isInCache(cur_city, time)){
                 // 2) 있다면 cache에 최근 쓴 걸 갱신
                answer += CACHE_HIT;
            }
            // 3) 없다면 
            else {
                // 4) 캐쉬에 빈자리가 있으면, push 없으면 pop push
                if(cache.size() == cacheSize)
                    cache.pop_back();
                cache.push_back({time, cur_city});
                answer += CACHE_MISS;
            }
        sort(cache.begin(), cache.end(), compare);
    }
    return answer;
}