📒활용개념

1. LRU(Least Recently Used Algorithm)

📌문제설명

지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터 베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 이에 어피치는 제이지를 도와 DB캐시를 적용할 때 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다. DB캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

• 입력형식
  - 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.

  • cacheSize는 정수이며, 범뉘는 0<=cacheSize<=30이다.
  • cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100000개이다.
  • 각 도시 이름은 공백, 숫자, 특수문자 등을 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

• 출력 형식
  - 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

• 조건
  - 캐시 교체 알고리즘은 LRU를 사용한다.

  • cache hit일 경우 실행시간은 1이다.
  • cache miss일 경우 실행시간은 5이다.

📌구현

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    if(cacheSize==0){					//cacheSize가 0일 경우
        return cities.size()*5;
    }
    
    int answer = 0;
    vector<string> que;					//cash역할을 하는 vector
    
    for(int i=0; i<cities.size(); i++){
        string check = cities[i];
        
        transform(check.begin(), check.end(), check.begin(), ::tolower);							//전부 소문자로 변환
        
        auto tmp=find(que.begin(), que.end(), check);	//cash에서 해당되는 data있는지 확인
        
        if(tmp==que.end()){								//없는 경우
            if(que.size()>=cacheSize){
                que.erase(que.begin());
                que.push_back(check);
                answer+=5;
            }
            else{
                que.push_back(check);
                answer+=5;
            }
        }

        else{											//있는 경우
            que.erase(tmp);
            que.push_back(check);
            answer+=1;
        }
    }
    
    return answer;
}

📌주의점

• LRU에 대한 이해가 필요하다.
• String에 대한 활용 함수를 얼마나 알고 있는지에 따라 문제 풀이의 정도가 달라진다.
• 캐시에 대한 컴퓨터 구조 개념도 함께 알 수 있었던 문제다.