Lv2_[[1차] 캐시, C++] 풀이 및 알고리즘 정리 - 프로그래머스

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

 

문제에서 반드시 알아야 할 부분은 '캐시 교체 알고리즘 LRU(Least Recently Used)'

• LRU는 가장 최근에 사용되지 않은 데이터를 우선적으로 교체하는 방식으로 캐시 메모리에 있는 데이터 중에서 가장 오랫동안 사용되지 않은 데이터를 제거하여 새로운 데이터를 캐시에 적재하는데 사용합니다.

 

• 크기가 3인 cache에 (JEJU, Pangyo, Seoul) 순차 삽입

캐시 순차 삽입

 

• 가득 차 있는 cache에  cache miss되는 문자열 삽입
  • 가장 오래된 JEJU는 삭제되고 새로운 LA 삽입

캐시 miss

 

• 가득 차 있는 cache에  cache hit되는 문자열 삽입
  
  • Pangyo가 hit되면 가장 최신의 위치로 이동됨

캐시 hit

위와 같은 동작을 고려해서

• 캐시는 list로 구성(양쪽으로 삽입 삭제가 용의한 자료형)
• 문자열 비교는 strcasecmp (대소문자 구분하지 않고 비교하는 함수)

 

알고리즘

1. 문자열 모음(vector<string> cities)에서 순차적으로 문자열 추출
2. 캐시(list<string> cache)에 일치하는 문자열 있는지 확인
   1. 일치하면(cache hit) 일치한 문자열을 가장 최신 위치로 이동
      • 실행 시간 + 1
   2. 일치하지 않으면(cache miss) 캐시에 문자열 저장
      • 실행 시간 + 5
      • 캐시가 가득 차 있으면 가장 오래된 문자열 삭제 후 저장
3. cities를 모두 탐색할 때까지 위의 동작 반복

#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <algorithm>
 
using namespace std;
 
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
 
    if(cacheSize == 0) {
        return cities.size() * 5;
    }
 
    list<string> cacheList;
    for(string city : cities) {
        list<string>::iterator cacheIter;
        for(cacheIter = cacheList.begin(); cacheIter != cacheList.end(); cacheIter++) {
            if(strcasecmp((*cacheIter).c_str(), city.c_str()) == 0) {
                break;
            }
        }
 
        if(cacheIter != cacheList.end()) {
            cacheList.erase(cacheIter);
            cacheList.push_back(city);
            answer += 1;
        } else {
            if(cacheList.size() >= cacheSize) {
                cacheList.pop_front();
            }
            cacheList.push_back(city);
            answer += 5;
        }
 
    }
 
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓