[c++][프로그래머스] 캐시

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

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

페이징 LRU 문제입니다. 특정 이름이 들어왔을 때, 캐시 안에 존재한다면 그대로 넣고 그렇지 않은 경우 변경하는 방식입니다.

 

가장 먼저, 캐시가 0인 경우에는 바로 곱셈해서 리턴합니다.

 

캐시가 있는 경우에는 지역명을 받아옵니다. 이때 transform을 이용해서 모두 대문자로 변경합니다.

 

만약 캐시에 같은 이름이 있다면 hit된 경우입니다. LRU 계산을 위해 카운트만 1로 변경합니다.

 

캐시에 같은 이름이 없다면, 캐시가 비어있는 경우와 그렇지 않은 경우로 나뉩니다.

 

캐시가 비어있는 경우, 캐시에 추가합니다.

캐시가 비어있지 않은 경우, 가장 오래된 즉 카운트가 가장 높은 인덱스를 골라서 변경합니다.

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    int city = cities.size();       // 도시의 수
    
    if(cacheSize == 0)
    {
        answer = city * 5;          // cache가 0인 경우 
        return answer;
    }
    
    vector<int> cache(cacheSize, 0);
    vector<string> name(cacheSize, "");
    
    int index = 0;
    int cacheIndex;
    bool find = false;
    
    for(int i=0; i<city; i++)
    {
        string str = cities[i];     // 도시 이름
        transform(str.begin(), str.end(), str.begin(), ::toupper);
            
        for(int j=0; j<cacheSize; j++)      // 캐시에 있는지 없는지 찾기
        {
            if(str == name[j])
            {
                cacheIndex = j;
                find = true;
                break;
            }
        }
        
        if(find == true)        // 있다면 -> hit!
        {
            cache[cacheIndex] = 1;
            answer += 1;
        }
        else                    // 없다면 -> miss
        {
            if(index < cacheSize)
            {
                cache[index] = 1;
                name[index] = str;
                index++;            // cache가 비어있다면 그대로 추가
            }
            else                    // 안 비어있다면
            {
                int big = 0;
                for(int k=0; k<cacheSize; k++)
                {
                    if(cache[k] > big)
                    {
                        big = cache[k];
                        cacheIndex = k;
                    }
                }
                
                cache[cacheIndex] = 1;
                name[cacheIndex] = str;
            }
            answer += 5;
        }
        
        for(int l=0; l<cacheSize; l++)
        {
            if(cache[l] > 0)
                cache[l]++;
        }
        
        find = false;
    }
    
    return answer;
}