[프로그래머스] 2018 KAKAO BLIND RECRUITMENT - [1차] 캐시, C++

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

코딩테스트 연습 - [1차] 캐시 | 프로그래머스

 본 문제는 '2018 KAKAO BLIND RECRUITMENT'로 kakao Tech에 의하면 "정답률 45.26%," 라고 한다. 난이도는 하로 구분되어 있다. 1차 코딩 테스트이기 때문에 난이도에 상관없이 정답률이 낮은 편이다. LRU 캐시 교체 알고리즘을 구현하는 문제로 LRU란 Least Recently Used의 약자로 페이지 교체 알고리즘에 해당한다.

 페이지 교체 알고리즘이란 OS에서 페이지 부재 시, 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것을 교체할지를 결정하는 알고리즘이다. LRU, FIFO(First In First Out), LFU(Least Frequently Used)가 있다.

#include <string>
#include <vector>
#include <iostream>
#include <map>
 
using namespace std;
 
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    map<string, int> m;
    // 캐시 크기가 0인 경우
    if (cacheSize == 0) return answer + (cities.size()*5);
    for (int i = 0; i < cities.size(); i++) {
        string tmp = "";
        for (int j = 0; j < cities[i].size(); j++) {
            if (cities[i][j]-'a' >= 0 && cities[i][j]-'a' <= 25) tmp += cities[i][j];
            else tmp += (cities[i][j]-'A')+'a';
        }
        cities[i] = tmp;
    }
    for (int i = 0; i < cities.size(); i++) {
        // 처음 입력된 캐시 등록
        if (m.find(cities[i]) == m.end()) {
            answer += 5;
            // 캐시용량이 부족할 때, 가장 오래 입력된 캐시 찾기
            if (m.size() == cacheSize) {
                auto min = 1e9;
                string tmp = "";
                for (auto it = m.begin(); it != m.end(); it++) {
                    if (min >= it->second) {
                        min = it->second;
                        tmp = it->first;
                    } 
                }
                m.erase(tmp);
                m.insert(make_pair(cities[i], i));
            }
            else m.insert(make_pair(cities[i], i));
        }
        // 캐시가 갱신되었을 때,
        else {
            answer += 1;
            m.erase(cities[i]);
            m.insert(make_pair(cities[i], i));
        }
    }
    return answer;
}