프로그래머스 - [1차] 캐시 [C++]

 이 문제는 자료구조를 이용한 구현 문제이다. cities의 최대 길이가 100,000 밖에 되지 않기 때문에 충분히 시간 안에 풀 수 있다. 일단 예외 케이스로 만약 캐시 사이즈가 0이라면 무조건 miss만 발생하기 때문에 5 * cities.size()를 리턴해주면 된다.

 

 

 그 다음 캐싱에 대한 알고리즘이 필요한데, 간략한 수도코드를 다음과 같이 구현했다.

먼저 찾을땐
	왼쪽에서 pop하면서 찾음 - 그 순서 그대로 집어넣음
	만약 찾으면 
		빼고 일단 왼쪽으로 집어넣음
		그 다음 찾은거 오른쪽으로 집어넣음
	만약 없으면
		일단 다 집어넣고 (왼쪽으로)
		가장 왼쪽에 있는거 빼고 오른쪽으로 새로 집어넣음

 물론 위와 같은 수도 코드를 그대로 구현하지는 않았지만, 생각을 정리하는데 큰 도움이 되었다. 덱에서 왼쪽에 있는 만큼 교체될 순위가 높은 것으로 간주하고 구현했다. 

 

 

 전체 코드는 다음과 같다.

#include <string>
#include <vector>
#include <deque>

using namespace std;

void toLower(string& input) {
    for (int i = 0; i < input.size(); i++) {
        char temp = input[i];
        
        if ('A' <= temp && temp <= 'Z') {
            input[i] += ('a' - 'A');
        }
    }
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    // base case
    if (cacheSize == 0) {
        return cities.size() * 5;
    }
    
    deque<string> cache;
    
    for (string& city : cities) {
        toLower(city);
        
        if (cache.empty()) {
            cache.push_back(city);
            answer += 5;
        }
        else if (cache.size() < cacheSize) {
            deque<string> tempCache;
            string hit = "";
            
            // 1. 찾기
            while (!cache.empty()) {
                string present = cache.front();
                cache.pop_front();
                
                if (present == city) {
                    hit = present;
                    break;
                }
                else {
                    tempCache.push_back(present);
                }
            }
            
            // 2. 원상복구
            while (!tempCache.empty()) {
                string present = tempCache.back();
                tempCache.pop_back();
                cache.push_front(present);
            }
            
            if (hit != "") {
                cache.push_back(hit);
                answer += 1;
            }
            else {
                cache.push_back(city);
                answer += 5;
            }
        }
        else {
            deque<string> tempCache;
            string hit = "";
            
            // 1. 찾기
            while (!cache.empty()) {
                string present = cache.front();
                cache.pop_front();
                
                if (present == city) {
                    hit = present;
                    break;
                }
                else {
                    tempCache.push_back(present);
                }
            }
            
            // 2. 원상복구
            while (!tempCache.empty()) {
                string present = tempCache.back();
                tempCache.pop_back();
                cache.push_front(present);
            }
            
            if (hit != "") {
                cache.push_back(hit);
                answer += 1;
            }
            else {
                cache.push_back(city);
                answer += 5;
                cache.pop_front();
            }
        }
    }
    
    return answer;
}