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

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

프로그래머스

---

문제 설명

캐시 크기에 따른 실행 시간을 측정하는 프로그램을 작성하시오.

캐시크키(cacheSize)와 도시이름 배열(cities)을 입력받습니다. (최대 캐시 사이즈 30, 최대 도시 수 10만개입니다)
각 도시 이름은 영문자로만 구성되어 있으며, 대소문자를 구분하지 않습니다.
캐시에 도시가 있어 캐시hit라면 1, 캐시에 도시가 없어 캐시 miss라면 5에 시간이 걸립니다.
캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용합니다.

* 페이지 교체 알고리즘(페이징 기법) : https://snikuz.tistory.com/78#002

FIFO(First In First Out) : 적재된 시간을 기준으로 페이지를 교체. 가장 먼저 할당한 페이지를 교체.
LFU(Leaset Frequently Used) : 최소 빈도로, 가장 사용 횟수가 적은 페이지를 교체.
LRU(Leaset Recently Used) : 가장 오래전에 참조된, 가장 안쓰던 페이지를 교체.
OPT(Optimal) : 앞으로 사용하지 않을 페이지를 교체.

---

아이디어

1. 대소문자 구분이 없다 → 대소문자 통일을 시켜야 할 것 같습니다.
2. 딕셔너리를 캐시용도로 쓰려고 합니다. 매 반복마다 모든 캐시에 사용 안된 턴을 증가합니다.
3. 캐시 사용시 턴을 초기화합니다.
4. 캐시가 꽉 찼다면 캐시 내에 가장 오래동안 사용 안한 캐시를 찾아 교체합니다.

---

코드

#include <bits/stdc++.h>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
	//캐시 사이즈 0일 때 예외처리
    if(cacheSize == 0) return cities.size() * 5;
    int answer = 0;
    
    unordered_map<string, int> m;
    for(auto& city : cities)
    {
    	//대소문자 통일
        for(int i = 0; i < city.size(); i++)
            city[i] = tolower(city[i]);
        
        if(m.find(city) == m.end())
        {
            if(m.size() < cacheSize)
            {
                m[city] = 0;
            }
            else
            {
                pair<string, int> target {"", -1};
                for(const auto& [key, value] : m)
                {
                    if(target.second < value)
                    {
                        target.first = key;
                        target.second = value;
                    }
                }
                m.erase(target.first);
                m[city] = 0;
            }
            answer += 5;
        }
        else
        {
            m[city] = 0;
            answer += 1;
        }
        for(auto& [key, value] : m)
            ++value;
    }
    
    return answer;
}

메모리 4.17MB, 시간 0.49ms