[프로그래머스] [1차] 캐시 (C++) - Lv.2

문제

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

프로그래머스

 

개요

문제 조건에 '캐시 교체 알고리즘은 LRU (Least Recently Used)를 사용한다.'라고만 명시되어 있고, LRU 알고리즘에 대한 설명은 없어서 약간은 당황했다.

 

물론, 학교 수업에서 LRU 교체 알고리즘에 대해 배운 적이 있어서 알고는 있었지만, 이렇게 PS에 등장하니까 약간 벙쪘었다.

 

LRU 교체 알고리즘은 가장 덜 최근에 사용된 것, 즉 가장 오랫동안 사용(혹은 참조)되지 않은 것을 교체하는 알고리즘이다.

다음은 LRU 교체 알고리즘을 나타낸 그림이다.

LRU 교체 알고리즘은 queue를 통해 구현할 수 있다.

queue의 앞쪽에 저장된 데이터일수록 가장 먼저 들어온 데이터인 것이다.

 

만약 cache hit, 즉 저장하려는 데이터가 기존의 queue에 존재한다면, 최근에 참조되었다는 내용을 명시하기 위해 해당 데이터를 queue의 기존 위치에서 제거한 후에, queue의 가장 마지막에 다시 삽입해준다.

 

반면, cache miss, 즉 저장하려는 데이터가 기존의 queue에 존재하지 않으면, 가장 오랫동안 사용되지 않은, 즉 queue의 맨 앞에 존재하는 데이터를 삭제해주고, 저장하려는 데이터를 queue에 삽입해준다.

 

정답 코드

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    deque <string> cache;
    
    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;
        }
    }
        
    for (int i = 0; i < cities.size(); i++){
        string city = cities[i];
        if (cacheSize == 0){
            answer += (5 * cities.size());
            break;
        }
        
        if (cache.empty()){ // cache 비어있는 경우 (맨 처음)
            cache.push_back(city); answer += 5;
            continue;
        }
        
        auto iter = find(cache.begin(), cache.end(), city);
        // cache 비어있지 않은 경우
        if (iter != cache.end()){ // cache hit
            cache.erase(iter);
            cache.push_back(city);
            answer += 1;
        }
        else{ // cache miss
            if (cache.size() < cacheSize){ // cache에 공간 남은 경우
                cache.push_back(city);
            }
            else{ // cache 꽉 찬 경우
                cache.pop_front();
                cache.push_back(city);
            }
            answer += 5;
        }    
    }
    return answer;
}

이 문제에서는 LRU 교체 알고리즘을 구현하는 부분 이외에도 주의할 점이 크게 2가지가 있다.

 

먼저, 각 도시 이름은 대소문자 구분을 하지 않는다는 문제 조건이 있다.

예를 들어, 테스트 케이스 5에서 NewYork과 newyork은 사실상 같은 데이터인 것이다.

그렇기 때문에, 도시 이름을 모두 소문자로 바꿔주거나, 모두 대문자로 바꿔주는 과정이 필요하다.

 

그 다음에는, cacheSize가 0인 경우를 고려해야 한다.

입력 형식을 보면, 0 <= cacheSize <= 30 이어서, cacheSize가 0인 경우도 가능하다.

즉, cache를 아예 사용하지 않는 경우도 있다는 것이다.

이 때는, 모든 경우가 cache miss이기 때문에 답은 간단하게 (도시 이름 개수) * 5 이다.

 

그리고, map에서는 map의 멤버 함수에 find가 있어서 m.find(str)과 같은 형태로 사용했었는데,

deque에는 find라는 멤버 함수가 없었다.

그래서, <algorithm> 헤더에 존재하는 find 함수를 사용했다.

이 find 함수는 찾으려는 값을 찾으면 해당 위치의 iterator를 반환하고, 찾지 못하면 end에 대항하는 iterator를 반환한다.

즉, 찾지 못하면, dq.end()를 반환하는 것이다.

(iterator를 변수로 받을 때, auto를 사용하면 편하다. auto는 자동으로 형식을 맞춰준다.)

 

더 깔끔한 정답 코드

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    deque <string> cache;
    
    if (cacheSize == 0){
        answer += (5 * cities.size());
        return answer;
    }
    
    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;
        }
    }
    
    for (int i = 0; i < cities.size(); i++){
        string city = cities[i];

        auto iter = find(cache.begin(), cache.end(), city);
        // cache 비어있지 않은 경우
        if (iter != cache.end()){ // cache hit
            cache.erase(iter);
            cache.push_back(city);
            answer += 1;
        }
        else{ // cache miss
            if (cache.size() == cacheSize){ // cache 꽉 찬 경우
                cache.pop_front();
            }
            cache.push_back(city);
            answer += 5;
        }    
    }
    return answer;
}

수정한 부분은 다음과 같다.

 

1) cacheSize == 0인 경우에 대한 if문은 굳이 for문 내부에 있지 않아도 되기 때문에, for문 밖으로 빼내어 solution 함수의 처음 부분에 작성해주었다.

 

2) 실행 맨 처음에 cache가 비어있는 경우에 대해 작성해준 if(cache.empty()) 문은 굳이 작성해주지 않아도, 이후에 작성되는 cache miss 구현 부분에서 처리되기 때문에 해당 if문은 삭제해주었다.

 

깨달은 점

학교 운영체제 수업 때 배운 LRU 교체 알고리즘에 PS에 등장해서 약간은 당황했다.

수업 시간에 잘 들어놓아서 다행이라는 생각이 들었다.

 

그리고, string의 모든 문자를 대문자로 변환하거나, 소문자로 변환하는 과정에 대해 간단한 방법이 있는지 찾아보았다.

#include <cctype> 을 하면 tolower, toupper 함수를 사용할 수 있다고 해서 사용해보았는데, 자꾸만 사용할 수 없다면서 오류가 떴다.

transfrom이라는 함수를 이용한 방법도 있었던 것 같은데, 이러한 방법은 나중에 실전에서 어차피 기억이 안 날 것 같아서 그냥 아스키코드 값을 이용하여 모두 소문자로 변환했다.

대문자에 32를 더하면 소문자다. 32라는 숫자가 기억이 안 나면 'a' - 'A' 를 이용하자.

 

그리고, iterator를 거의 사용해보지 않아서, 약간 얼탔던 부분도 있다.

특히, deque의 erase 함수를 사용할 때는 인자로 정수 형태의 index가 아닌 iterator를 대입해주어야 한다는 사실을 알 수 있었다.