C++ [1차] 캐시

 

---

 

#include <string>
#include <vector>
#include <list>
#include <unordered_map>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    // 데이터를 저장할 list
	list<string> LRUList;

	// 참조를 저장할 map
	unordered_map<string, list<string>::iterator> LRUMap;

	// 최대 용량
	int LRUMaxSize=cacheSize; 
    int answer = 0;
    
    // 캐시 크기가 0인 경우 예외 처리
    if(LRUMaxSize==0)
    {
        answer=cities.size()*5;
        return answer; 
    }
    
    // 소문자 다 대문자로 통일
    for(int i=0;i<cities.size();i++)
    {
        for (char& _Ch : cities[i])
	    {
            
		_Ch = std::toupper(_Ch);
            
	    }	    
    }
    
    // LRU 알고리즘
    for(int i=0;i<cities.size();i++)
    {
        // 캐시 내에 없을 경우
	if (LRUMap.find(cities[i]) == LRUMap.end()) {
		// 캐시가 꽉 찼을 경우
		if (LRUList.size() == LRUMaxSize) {
			string last = LRUList.back();

			// 리스트에서 가장 오래 사용되지 않은 요소 pop
			LRUList.pop_back();

			// 참조도 함께 삭제
			LRUMap.erase(last);
		}
        answer+=5;
    }
    else // 캐시 내에 있을 경우 해당 요소 삭제
    {
        LRUList.erase(LRUMap[cities[i]]);
        answer+=1;
    }

	// 새로운 요소 x를 맨 앞에 push, 참조도 updqte
	LRUList.push_front(cities[i]);
	LRUMap[cities[i]] = LRUList.begin();
    }
    
    return answer;
}