캐시

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

2018년 카카오 블라인드 코딩 테스트

캐시 사이즈가 0일 때는 cities.size() * 5를 return 하면 된다.

캐시.xlsx

#include <bits/stdc++.h>
 
using namespace std;    
 
map<int, string> m;
 
int solution(int cacheSize, vector<string> cities) 
{
    int answer = 0, t = 1;
 
    if (cacheSize == 0)
        return cities.size() * 5;
    
    for (auto now : cities)
    {
        string uppernow = "";
 
        for (auto i : now)
            uppernow += toupper(i);
 
        // 꽉 찬 경우
        if (m.size() == cacheSize)
        {
            bool hit = false;
 
            for (auto i : m)
                if (i.second == uppernow)
                {
                    answer += 1; // 캐시 히트
                    hit = true; 
                    m.erase(i.first); // 삭제하고
                    m[t] = uppernow; // 새로운 시간(키값)에 대한 uppernow 추가
                    break;
                }
 
            if (!hit) // 캐시 히트가 아니라면, 교체 발생(= 캐시 미스)
            {
                for (auto i : m)
                {
                    m.erase(i.first); // 가장 오래 사용되지 않은 것 제거
                    break;
                }
 
                m[t] = uppernow; // 추가
                answer += 5;
            }
        }
        else // 아직 공간이 있는 경우
        {
            bool hit = false;
 
            for (auto i : m) // 이미 있는지 검사
                if (i.second == uppernow) // 있다면, 캐시 히트
                {
                    answer += 1; // 캐시 히트
                    hit = true;
                    m.erase(i.first); // 시간 갱신을 위해 제거
                    m[t] = uppernow; // 새로운 시간에 대해 다시 추가
                    break;
                }
            
            if (!hit) answer += 5, m[t] = uppernow; // 캐시 미스
        }
 
        ++t;
    }
 
    return answer;
}
 
int main(void)
{
    /*vector<string> cities = {
        "Jeju", 
        "Pangyo", 
        "Seoul", 
        "Jeju", 
        "Pangyo", 
        "Seoul", 
        "Jeju", 
        "Pangyo", 
        "Seoul"
    };*/
 
    /*vector<string> cities = {
        "Jeju",
        "Pangyo",
        "Seoul",
        "NewYork",
        "LA",
        "Jeju",
        "Pangyo",
        "Seoul",
        "NewYork",
        "LA"
    };*/
 
    /*vector<string> cities = {
    "Jeju",
    "Pangyo",
    "NewYork",
    "newyork"
    };*/
 
    vector<string> cities = {
        "Aa",
        "aa",
        "Bb",
        "bB",
        "C"
    };
 
    printf("%d\n", solution(0, cities));
    
    return 0;
}