문제

부끄럽게도 LRU가 살짝 헷갈려서 찾아보고 옴^^ 뎈을 사용해 풀었다. 그리고 특정 아이템이 캐시에 있는지 빠르게 확인하기 위해 맵도 함께 사용했다.

#include <string>
#include <vector>
#include <deque>
#include <map>
using namespace std;

deque<string> dq;
map<string, int> m;

void reorderCache(string item) {
	// find idx of the item in deque
	int idx = 0, size = dq.size(), i;
	while (dq.at(idx) != item) idx++;

	// pop item
	for (i = 0; i < idx; i++) {
		string tmp = dq.front();
		dq.pop_front();
		dq.push_back(tmp);
	}
	dq.pop_front();
	for (i = 0; i < size - (idx + 1); i++) {
		string tmp = dq.front();
		dq.pop_front();
		dq.push_back(tmp);
	}

	// push the item to the front
	dq.push_front(item);
}

void updateCache(int cacheSize) {
	while (dq.size() > cacheSize) {
		string now = dq.back();
		dq.pop_back();
		m[now]--;
	}
}

int solution(int cacheSize, vector<string> cities) {
	int answer = 0, i;

	for (string city : cities) {
		for (i = 0; i < city.size(); i++) { // 대소문자 무시
			city[i] = tolower(city[i]);
		}
		if (m[city]) { // cache hit
			reorderCache(city);
			answer += 1;
		}
		else { // cache miss
			if (cacheSize) {
				m[city]++;
				dq.push_front(city);
				updateCache(cacheSize);
			}
			answer += 5;
		}
	}
	return answer;
}