[프로그래머스] 캐시

20 Jun 2025 • munjjang9

Programmers - [2018 KAKAO BLINE RECRUITMENT] 캐시

사용 언어 - C++

소요 시간 - 42분

정답 여부 - O

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17680

문제 요약

캐시 사이즈와 도시 이름이 담긴 배열이 주어짐
도시 이름은 대소문자 구분 없이
캐시 교체 알고리즘 : LRU(Least Recently Used)
캐시 히트 : 실행시간 += 1
캐시 미스 : 실행시간 += 5
return 실행시간

ex)
캐시 사이즈가 4인 캐시에
🌙❤️⭐🌟 순서로 저장되어 있다고 할 때,
🌙를 넣는다고 가정하면, 캐시 내부에 🌙가 있기 때문에 캐시 히트,
❤️⭐🌟🌙 이렇게 저장이 됨. 실행시간 + 1

🌙❤️⭐🌟 순서로 저장되어 있다고 할 때,
🌕를 넣는다고 가정하면, 캐시 내부에 🌕가 없기 때문에 캐시 미스,
❤️⭐🌟🌕 이렇게 저장이 됨.
실행시간 + 5

최종 코드

#include <string>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

void ToUpper(vector<string>& InString)
{
    for(int i = 0; i < InString.size(); i++)
        for(int j = 0; j < InString[i].length(); j++)
            InString[i][j] = toupper(InString[i][j]);
    
    return;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    ToUpper(cities);
    
    list<string> caches;
    
    for(int i = 0; i < cities.size(); i++)
    {
        list<string>::iterator iter = find(caches.begin(), caches.end(), cities[i]);
        
        bool cacheMiss = (iter == caches.end());
        
        if(cacheMiss)
        {
            if(caches.size() < cacheSize)
            {
                caches.push_back(cities[i]);
            }
            else if(cacheSize > 0 && caches.size() == cacheSize)
            {
                caches.erase(caches.begin());
                caches.push_back(cities[i]);
            }
            
            answer += 5;
        }
        else
        {
            caches.erase(iter);
            caches.push_back(cities[i]);
            answer += 1;
        }
    }
    
    return answer;
}

트러블 슈팅

문제가 발생한 건 아니지만, 처음 풀어보는 류의 문제여서 생각하는데 조금 시간이 걸렸다

문제 풀이 후 소감

큐로 풀지, 리스트로 풀지 고민하다가 원소의 삽입, 삭제가 빠른 리스트로 풀어보기로 했다. 리스트는 코테에서 처음 써봐서 아직은 익숙하지 않아 문제를 푸는 데 생각보다 오랜 시간이 걸렸다. 다음에 풀 때는 조금 덜 걸리겠지…?

coding-test