PROGRAMMERS 캐시 (2018 KAKAO BLIND RECRUITMENT)

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

프로그래머스

 

0. 문제 개요

구현 문제.

캐시 사이즈와 도시 목록이 주어진다.

도시 목록을 차례대로 읽으며 캐시 내 도시 이름이 있는지 확인한다. (LRU) Least Recently Used 알고리즘에 따라 캐시 목록을 업데이트한다. 현재 탐색하는 도시 이름이 캐시 내 존재하면 비용을 +1, 존재하지 않으면 +5만큼 증가시킨다.

도시 목록 탐색이 완료되었을 때 비용을 리턴한다.

 

 

 

1. 문제 해결 아이디어

 1-1. 초기 아이디어

캐시 사이즈가 30 밖에 되지 않으므로 캐시 사이즈만큼 배열을 만들어서 방문 history를 기록하고자 했다. 가령 5번째 도시에서 2번 캐시가 방문되었으면 2번 history 배열을 5로 업데이트하는 방식이다.

 

-> 채점했을 때 2개의 테스트 케이스를 통과하지 못했다...

 

 1-2. 새로운 아이디어

캐시에 저장된 순서에 방문 history를 반영한다. 다시 말해서 캐시 vector에서 가장 앞에 저장된 것일수록 방문한 지 오래된 도시가 된다. 이는 LRU 알고리즘에 따라 가장 먼저 캐시에서 배출되어야 할 대상이다.

(주의) 어떤 도시 이름이 캐시 내 존재할 때에도 해당 도시 이름을 캐시에서 제거하고 다시 캐시 맨 뒤에 위치시켜야 한다. (방문 순서 update)

 

 

 

 

2. 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> cache;
int solution(int cacheSize, vector<string> cities) {
 
    int answer = 0;
 
    for (int i = 0; i < cities.size();i++) {                //도시이름 소문자화
        for (int j = 0; j < cities[i].size();j++) {
            if ('A' <= cities[i][j] && cities[i][j] <= 'Z') {
                cities[i][j] += 32;
            }
        }
    }
    vector<string>::iterator it;
 
    for (string x : cities) {
 
        it = find(cache.begin(), cache.end(), x);
 
        if (cacheSize == 0) {
            answer += 5;
        }
        else {// cacheSize > 0
            if (it == cache.end()) {     //cache에 없으면
                answer += 5;
                if (cache.size() < cacheSize) {    //cache 자리 남으면
                    cache.emplace_back(x);
                
                }
                else {    //cache 자리 없으면
                    cache.erase(cache.begin());    //맨 앞 노드를 제거한다.
                    cache.emplace_back(x); //새로운 노드를 맨 뒤에 추가한다.
                }
            }
            else { //cache에 있으면
                answer += 1;
                cache.erase(it);    //해당 노드 삭제
                cache.emplace_back(x); //새로운 노드를 맨 뒤에 추가한다.(방문 순서 업데이트)
            }
        }
    }
 
    return answer;
}