[ 프로그래머스 ] [1차] 캐시 2018 KAKAO BLIND RECRUITMENT

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

문제의 설명은 다음과 같다.

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

• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.

• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

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

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

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

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

문제 접근을 잘못해서 푸는데 오래 걸렸다..

반성할 점 1 -> 알고리즘을 검증없이 사용

• 이 문제는 LRU방식으로 cache의 내용을 교체하지만 내가 짠 코드는 sliding window알고리즘으로 교체를 한다.
• LRU 방식으로 구현하는 것이 결국에 sliding window로 하는 거랑 같다고 생각했는데 이는 틀린생각이다.
• 예를 들어 cache size가 3이고 입력이 BCACD라고 하면
  LRU방식은 처음으로 제거 되는 원소가 B이지만 sliding window는 C이다. 둘이 완전다른데 직관적으로 결국 결과가 같다고 생각했다...(요즘 caterpillar method를 많이 풀어서 그런것 같다..)
• 왠만하면 문제에서 알고리즘을 제시하면 직접 구현하는것이 제일 안전하다. 문제에서 제시하는 알고리즘을 내가 아는 다른 알고리즘과 결과가 같을거라고 생각하지 말자. 만약 그럴거면 증명하고 풀어야 한다.

반성할 점 2 -> cache size를 보고 1을 피했어야함

• cache size가 30이라는 것을 통해 알수있는건 최근에 쓰인 job을 계속 위치를 바꿔줘도 된다는 뜻이다. 즉 lru를 직접 구현하란 뜻이다. 하지만 set에 꽂혀서 그럴 생각을 못했다.

반성할 점 3 -> cold miss와 cache의 초기 상태를 잘못 생각했다.

• 처음에 cacheSize만큼만 cache에 넣으면 cache가 가득 찰거라고 생각했는데 첨부터 중복되는 원소가 올수있다. 이를 간과했다.
  즉 초기상태역시 맘대로 생각하지 말고 simulation을 해야한다.

알고리즘

• cache 삽입 알고리즘
  • hit
    • 삽입 하려는 원소가 존재하면 그 원소를 삭제하고 deque의 가장 앞에 다시 삽입한다.
    • hit counter를 증가 시킨다.
  • miss
    • 삽입하려는 원소가 존재하지 않는다면 deque의 가장 앞이 삽입한다.
    • miss counter를 증가시킨다.
• 1. cache에 cold miss가 나지 않을때까지 즉 cache가 가득찰때까지 원소를 삽입한다.
• 2. 가득찬 경우 그 인덱스 부터 cities.size까지 삽입한다.
• 3. miss_counterx5+hit_counter를 리턴한다.

코드

#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
void lowerFunction(string &s){
    for(int i=0;i<s.length();i++)
        if('A'<=s[i] and s[i]<='Z') s[i]+='a'-'A';
}
void InsertAlgorithm(deque<string>& s,int cacheSize,string target,int& miss,int& hit){
    if(cacheSize==0){
        miss++;
        return;
    }
    if(find(s.begin(),s.end(),target)==s.end()) {
        s.push_front(target);
        if(s.size()>cacheSize) s.pop_back();
        miss++;
        }
   else{
        s.erase(find(s.begin(),s.end(),target));
        s.push_front(target);
        hit++;
    }
}
int solution(int cacheSize, vector<string> cities) {
    int hit=0;
    int miss=0;
    int end=0;
    deque<string> s;
    
    for(int i=0;i<cities.size();i++) lowerFunction(cities[i]);
    
    while(s.size()<cacheSize&& end<cities.size()){
        InsertAlgorithm(s,cacheSize,cities[end],miss,hit);
        end++;
    }
    for(int i = end; i< cities.size();i++) InsertAlgorithm(s,cacheSize,cities[i],miss,hit);
    return miss*5+hit;
}