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

2018 KAKAO BLIND RECRUITMENT (2018 카카오 블라인드 채용 문제)

캐시 크기가 주어질때 해당 도시들을 검색할 때 실행 시간을 구하는 문제입니다.

캐시 교체 알고리즘은 LRU를 사용합니다.

*LRU (Least Recently Used) : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

4번째 예제의 경우 
                              <------ 최근 참조 ------ 오랜된 참조 ------>
(cache miss)   1. 캐시 : Jeju                                                      실행시간 : 5초
(cache miss)   2. 캐시 : Pangyo, Jeju                                           실행시간 : 10초
(cache miss)   3. 캐시 : Seoul, Pangyo, Jeju                                  실행시간 : 15초
(cache miss)   4. 캐시 : NewYork, Seoul, Pangyo, Jeju                     실행시간 : 20초
(cache miss)   5. 캐시 : LA, NewYork, Seoul, Pangyo, Jeju                실행시간 : 25초
(cache miss)   6. 캐시 : SanFrancisco, LA, NewYork, Seoul, Pangyo    실행시간 : 30초
( cache  hit )   7. 캐시 : Seoul, SanFrancisco, LA, NewYork, Pangyo    실행시간 : 31초
(cache miss)   8. 캐시 : Rome, Seoul, SanFrancisco, LA, NewYork      실행시간 : 36초
(cache miss)   9. 캐시 : Paris, Rome, Seoul, SanFrancisco, LA            실행시간 : 41초
(cache miss)   10. 캐시 : Jeju, Paris, Rome, Seoul, SanFrancisco         실행시간 : 46초
(cache miss)   11. 캐시 : NewYork, Jeju, Paris, Rome, Seoul             실행시간 : 51초
( cache  hit )   12. 캐시 : Rome, NewYork, Jeju, Paris, Seoul             실행시간 : 52초

해결 방법

1. 입력받은 도시들을 소문자로 변환
2. 캐시 사이즈가 0이면 도시 * 5를 반환 (종료)
3-1. 캐시 현재 용량이 0이면 도시 삽입, 시간 + 5초
3-2. 캐시에 현재 찾는 도시가 있는 경우, 해당 도시를 캐시 가장 앞부분에 이동, 시간 + 1초
3-3. 캐시에 찾는 도시가 없는 경우
3-3-1. 캐시사이즈와 용량이 동일한 경우, 가장 오래된 캐시 데이터 삭제, 검색중인 도시 캐시에 삽입, 시간 + 5초
3-3-2. 캐시사이즈와 용량이 동일하지 않은 경우, 검색중인 도시 캐시에 삽입, 시간 + 5초
4. 도시를 전부 검색할 때까지 3번 반복

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int solution(int cacheSize, vector<string> cities)
{
  bool check = false;
  int answer = 0;
  vector<string> cache;
  vector<string> temp;
  for (int i = 0; i < cities.size(); ++i)
  {
    for (int j = 0; j < cities[i].length(); ++j)
    {
      cities[i][j] = tolower(cities[i][j]);
    }
    if(cacheSize == 0){
      return cities.size() * 5;
    }
    if (cache.size() == 0)
    {
      cache.push_back(cities[i]);
      answer += 5;
      continue;
    }
    for (int j = 0; j < cache.size(); ++j)
    {
      if (cities[i] == cache[j])
      {
        temp.clear();
        temp.push_back(cities[i]);
        cache.erase(cache.begin() + j);
        temp.insert(temp.end(), cache.begin(), cache.end());
        cache = temp;
        ++answer;
        check = true;
        break;
      }
    }
    if (check)
    {
      check = false;
      continue;
    }
    if (cache.size() == cacheSize)
    {
      cache.erase(cache.end() - 1);
    }
    temp.clear();
    temp.push_back(cities[i]);
    temp.insert(temp.end(), cache.begin(), cache.end());
    cache = temp;
    answer += 5;
    continue;
  }

  return answer;
}