[2023년 11월 23일][1차]캐시(22분: 90점)

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

구현 아이디어 5분 구현 17분

풀이

7, 17 반례. cacheSize가 0일 경우이다.

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

// 7, 17 테스트 케이스 실패.
// 반례: cacheSize가 0일 경우.

using namespace std;

map<string, int> records;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    // 7, 17 테스트 케이스 조건 해결.
    if(cacheSize == 0)
    {
        answer = cities.size() * 5;
        return answer;
    }
    
    for(int i = 0; i < cities.size(); ++i)
        for(int j = 0; j < cities[i].length(); ++j)
            if(isupper(cities[i][j])) cities[i][j] = tolower(cities[i][j]);
    
    int limit = 0;
    int time = 0;
    for(int i = 0; i < cities.size(); ++i)
    {
        // 일단 캐시에 있는지 없는지 검사.
        if(records[cities[i]])
        {
            // 캐시에 있다.
            time += 1;
            records[cities[i]] = time;
        }
        else
        {
            time += 5;
            if(limit < cacheSize)
            {
                // 아직 캐시에 공간이 있다.
                records[cities[i]] = time;
                ++limit;
            }
            else
            {
                // 가장 오래 전에 쓰인 캐시 찾아 0으로 초기화.
                string min_key;
                int min_value = 2147000000;
                
                for(auto& it : records)
                {
                    if(it.second && it.second < min_value)
                    {
                        min_value = it.second;
                        min_key = it.first;
                    }
                }
                records[min_key] = 0;
                records[cities[i]] = time;
                //printf("i: %d   min_key: %s   min_value: %d\n", i, min_key.c_str(), min_value);
            }
        }
    }
    
    return answer = time;
}