Programmers - 캐시

---

title: Programmers - 캐시
date: 2022-06-25
tags:

• Algorithm

---

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

문제 요약

LRU 방식의 캐시 크기와 도시 리스트가 주어진다. Cache hit일 경우 시간이 1, miss일 경우 5가 소요된다. 주어진 도시와 캐시들을 이용하였을 때 소요 시간을 구하여 return한다.

문제 풀이

LRU 캐시 적용이므로 앞에서부터 순차적으로 확인하면 된다.
캐시를 저장할 string vector 한 개, 언제 사용되었는지 저장할 int 배열 한 개 이용한다.
Miss라면 가장 값이 작은(저장이 제일 오래전에 이루어진) 캐시의 값을 바꾼다.

대문자와 소문자의 구분이 없고, 일일히 대치하는 for문 대신 실무에서 이용할만한 방법을 찾았다.
How to convert an instance of std::string to lower case
Java의 toLowerCase 같은 함수가 없고 각 character를 순차적으로 확인하며 대치해주어야 한다.
for문 대신 대치를 해줄 함수를 선언하고, 이 함수를 transform의 파라미터로 넣어주면 알아서 처리가 된다.

transform 함수의 경우 파라미터가 4개 혹은 5개이다.

4개일 경우, (Start , End , Save, Function) - Start부터 End 전까지 Function의 파라미터로 사용하여 결과를 Save부터 순서대로 저장한다.
5개일 경우, (Start1 , End1 , Start2 , Save, Function) - Start1부터 End1 전까지 Function의 첫 번째 파라미터로, Start2부터 같은 개수를 Function의 두 번째 파라미터로 사용하여 결과를 Save부터 순서대로 저장한다.

간단히 Function의 파라미터의 개수에 따라 두 가지로 나누어 사용할 수 있는 것이다.
보통 PS의 경우 transform 함수 대신 for문으로 사용하는 편이지만, 실무에서 사용하기에는 정말 좋은 함수인 것 같다.

추가적으로, LRU 방식은 결국 queue와 동일한 방식이다.
그렇기에 이렇게 2개의 배열을 이용하기 보다는 queue를 도입하는 것이 훨씬 좋은 프로그램이라 생각한다.

프로그램

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

using std :: vector ;
using std :: string ;

char chToLowerCase ( char ch )
{
    if ( 'a' <= ch )
        ch -= 32 ;

    return ch ;
}

int solution ( int cacheSize , vector < string > cities )
{
    int answer = 0 ;
    vector < string > vCache ;
    vCache.resize ( 30 ) ;
    int irgCache [ 30 ] = { 0 , } ;
    string * strpTemp = cities.data () ;
    string * strpCache = vCache.data () ;
    int iCitySize = cities.size () ;
    bool bCacheMiss = true ;



    std :: fill ( irgCache , irgCache + 30 , -1 ) ;    // Fill with -1 to replace first

    if ( 0 == cacheSize )
        return 5 * iCitySize ;

    for ( int i = 0 ; i < iCitySize ; ++i )            // Each city
    {
        string strLower = strpTemp [ i ] ;
        std :: transform ( strLower.begin () , strLower.end () , strLower.begin () , chToLowerCase ) ;
        bCacheMiss = true ;

        for ( int j = 0 ; j < cacheSize ; ++j )
        {
            if ( 0 == strLower.compare ( strpCache [ j ] ) )        // If hit
            {
                bCacheMiss = false ;
                ++ answer ;
                irgCache [ j ] = i ;

                break ;
            }
        }

        if ( bCacheMiss )
        {
            int iIndex = 0 ;

            for ( int j = 1 ; j < cacheSize ; ++j )
            {
                if ( irgCache [ j ] < irgCache [ iIndex ] )
                {
                    iIndex = j ;
                }
            }

            irgCache [ iIndex ] = i ;
            strpCache [ iIndex ] = strLower ;

            answer += 5 ;
        }
    }


    return answer ;
}