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

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

프로그래머스

풀이

LUR 알고리즘을 사용해서 DB 캐시를 적용할 때 캐시 크기에 따른 실행시간을 측정하는 프로그램을 구현하는 문제입니다.

 

일단 LUR 알고리즘에 대해 잘 몰랐기 때문에 찾아본 내용을 정리하자면,

 

cache_hit이란 cpu가 참조하고자 하는 메모리가 캐시에 존재할 때,

cache_miss 란 그 반대의 경우를 말합니다.

 

LUR 을 구현하기 위해서는 데이터를 저장하기 위한 list 자료구조와 이를 추적하기 위한 해시 맵이 필요합니다. 

새로 들어온 데이터가 캐시에 존재한다면, 가장 뒤의 데이터를 지우고 list의 가장 앞에 push 합니다.

그 외의 경우 즉 캐시에 데이터가 없다면, 그리고 캐시가 꽉 차있다면 가장 뒤의 데이터를 삭제합니다. 이때, 캐시가 꽉 차있지 않다면 데이터를 지우지 않습니다.

 

문제에서 주어진대로 시간을 계산합니다. 이때, 캐시 크기가 0인 경우 모두 cache_miss 로 계산하여 리턴합니다.

그리고, 문자의 대소문자를 구별하지 않는 것에 주의하여 모두 소문자로 변환하여 lru 리스트에 넣어주었습니다.

 

#include <string>
#include <vector>
#include <list>
#include <unordered_map>
#include <iostream>
using namespace std;

class LRU {
	// 데이터를 저장할 list
	list<string> LRUList;

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

	// 최대 용량
	int LRUMaxSize; 
    int time = 0;
    
public:
	LRU(int);
	void refer(string);
	void display();
    int calc_time();
};

// 클래스가 생성될 때 크기를 선언함.
LRU::LRU(int n)
{
	LRUMaxSize = n;
}

// 요소 x를 참조하는 함수 refer
void LRU::refer(string x)
{
	// 캐시 내에 없을 경우
	if (LRUMap.find(x) == LRUMap.end()) {
		// 캐시가 꽉 찼을 경우
		if (LRUList.size() == LRUMaxSize) {
			string last = LRUList.back();

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

			// 참조도 함께 삭제
			LRUMap.erase(last);
		}
        time += 5;
	}

	// 캐시 내에 있을 경우 해당 요소 삭제
	else {
        LRUList.erase(LRUMap[x]);
        time += 1;
    }
		
	// 새로운 요소 x를 맨 앞에 push, 참조도 update
	LRUList.push_front(x);
	LRUMap[x] = LRUList.begin();
}

int LRU::calc_time() 
{ 
    return time;
}
// 요소 x를 참조하는 함수 refer
void LRU::display()
{
	for (auto it = LRUList.begin(); it != LRUList.end(); it++) {
		cout << (*it) << " ";
	}

	cout << endl;
}

int cache_miss = 5;
int cache_hit = 1;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    LRU lru(cacheSize);
    if (cacheSize == 0) {
        return cities.size() * cache_miss;
    }
    
    for (int i=0; i < cities.size(); i++) {
        for (int j=0; j<cities[i].size(); j++) {
            cities[i][j] = tolower(cities[i][j]);
        }
        lru.refer(cities[i]);
    }

    return lru.calc_time();
}