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

문제

---

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

풀이

---

LRU(Least Recently Used) 알고리즘은 가장 오래 쓰이지 않은 것을 뽑아 교체하는 알고리즘으로, 이를 구현하는 문제이다. 캐시에 원하는 데이터가 있는 경우를 hit라고 하며, 이를 뽑아 맨 뒤에 넣고(가장 최근에 쓴), 캐시에 원하는 데이터가 없는 경우를 miss라고 하며, 가장 앞에 있는 데이터를 뽑고(가장 오래 쓰이지 않은)맨 뒤에 데이터를 추가한다. 이를 vector로 구현하여 주어진 배열 원소와 캐시 배열 원소를 비교하여 hit, miss를 판단하여 실행 시간을 구한다. 단, 캐시 사이즈가 0일 경우는 모두 miss로 판단하여 주어진 배열 크기 x miss 값을 return한다.

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

int solution(int cacheSize, vector<string> cities)
{
    int answer = 0;
    int cacheHit = 1;
    int cacheMiss = 5;
    vector<string> arr;

    if (cacheSize == 0)
    {
        answer += (cacheMiss * cities.size());
        return answer;
    }

    for (int i = 0; i < cities.size(); i++)
    {
        if (arr.size() == 0)
        {
            arr.push_back(cities[i]);
            answer += cacheMiss;
        }

        else
        {
            for (int j = 0; j < arr.size(); j++)
            {
                if (!strcasecmp(cities[i].c_str(), arr[j].c_str()))
                {
                    if (arr.size() < cacheSize)
                    {
                        arr.push_back(cities[i]);
                        answer += cacheHit;
                    }

                    else
                    {
                        arr.push_back(cities[i]);
                        arr.erase(arr.begin() + j);
                        answer += cacheHit;
                    }

                    break;
                }

                if (j == arr.size() - 1)
                {
                    if (arr.size() < cacheSize)
                    {
                        arr.push_back(cities[i]);
                        answer += cacheMiss;
                    }
                    
                    else
                    {
                        arr.erase(arr.begin());
                        arr.push_back(cities[i]);
                        answer += cacheMiss;
                    }

                    break;

                }

            }
        }

    }


    return answer;
}