[2018 KAKAO BLIND RECRUITMENT] [1차] 캐시

#define cache_hit 1
#define cache_miss 5

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
map<string, int> LRU_Cache;

int solution(int cacheSize, vector<string> cities) {
    int exe_time = 0;  
	map<string, int>::iterator iter;
	map<string, int>::iterator erase_iter;
    
    // 대소문자 구분을 안하므로, 모두 소문자로 변경해 놓는다.
	for (int i = 0; i < cities.size(); i++) {
		for (int j = 0; j < cities[i].size(); j++) {
			cities[i][j] = tolower(cities[i][j]);
		}
	}
    
    for (int i = 0; i < cities.size(); i++) {

		iter = LRU_Cache.find(cities[i]); // 캐시에 있는지 없는지 판단

		// Cache size가 0, 즉 캐시가 없을 경우는 특이 Case로 100% miss
		if (cacheSize == 0) exe_time += cache_miss;

		// (1) LRU_Cache에 해당 요소가 존재하지 않을 경우
		else if (iter == LRU_Cache.end()) {
			// miss++
			exe_time += cache_miss;

			// map size가 정해진 cacheSize 보다 작을 경우,
            // 캐시 내에 빈 공간이 있다는 의미이므로,
            // 캐시 내부 모든 요소의 순위 값을 1씩 증가시키고
			// 새로 들어갈 것을 insert 한다.
			if (LRU_Cache.size() < cacheSize) {
				for (iter = LRU_Cache.begin(); iter != LRU_Cache.end(); iter++) {
					iter->second += 1;
				}
				LRU_Cache.insert({ cities[i], 0 });
			}

			// 캐시가 꽉 찼을 경우, 순위 값이 가장 큰 것을 지우고,
            // 캐시 내부 모든 요소의 순위 값을 1씩 증가시킨 다음,
            // 새로 들어갈 것을 insert 한다.
			else {
				int max_value = -1;
				for (iter = LRU_Cache.begin(); iter != LRU_Cache.end(); iter++) {
					if (max_value < iter->second) {
						max_value = iter->second;
						erase_iter = iter;
					}
				}
				LRU_Cache.erase(erase_iter);
				for (iter = LRU_Cache.begin(); iter != LRU_Cache.end(); iter++) {
					iter->second += 1;
				}
				LRU_Cache.insert({ cities[i], 0 });
			}
		}	

		// (2) LRU_Cache에 해당 요소가 존재할 경우
		else {
			// hit++
			exe_time += cache_hit;

			// 찾은 요소를 가장 최신으로 만들어야 한다.
			iter->second = 0;

			for (iter = LRU_Cache.begin(); iter != LRU_Cache.end(); iter++) {
				// 다른 모든 요소의 LRU 값을 1 증가시킨다.
				if (iter->first != cities[i]){
					iter->second += 1;
				}
			}
		}
	}
    
    return exe_time;
}