카카오 2017 블라인드 테스트 1차: 캐시 (C++)

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

현재 캐시의 크기와, 사용 빈도에 관련된 정보를 배열을 활용해서 계속 검사해주며 miss와 hit 여부를 판단해주면 된다.

주의할 것은, 대소문자에 상관없이 비교를 하기 때문에 (Seoul과 seoul이 둘 다 입력으로 들어올 수 있는데, 같다고 판단해야 함) 이 부분을 잘 확인하면 된다.

어떤 문자열을 소문자로 변환하는 경우, algorithm 헤더에 있는 transform 함수를 이용한다.

파라미터는 transform(변환할 문자열의 시작주소, 변환할 문자열의 끝주소, 변환 결과를 저장할 문자열의 시작주소, ::변환방식)이다.

transform(ct[i].begin(), ct[i].end(), ct[i].begin(), ::tolower);

이런식으로 사용해준다.

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
#include <string.h>
using namespace std;
int used[31], curSize = 0;
string cache[31];
int findCity(string city){
    for(int i = 0 ; i < curSize ; i++){
        if(cache[i] == city) return i;
    }
    return -1;
}
int solution(int sz, vector<string> ct) {
    int ans = 0;
    for(int i = 0 ; i < ct.size() ; i++){
        transform(ct[i].begin(), ct[i].end(), ct[i].begin(), ::tolower);
      
        int findIdx = findCity(ct[i]);
        if(findIdx >= 0){ //캐싱되어있는 경우
           ans++;
            for(int j = 0 ; j < curSize ; j++)
                used[j]++;
            used[findIdx] = 0;
        }
        else{
            //캐시 미스라서 추가해야 하는데 자리가 있는/없는 경우
            if(curSize < sz){ //자리 있
                cache[curSize] = ct[i];
                curSize++;
            }
            else{ // 자리 없
                int leastCnt = -1, idx = 0;
                for(int j = 0 ; j < curSize ; j++){
                    if(used[j] > leastCnt){
                        leastCnt = used[j];
                        idx = j;
                    }
                }
                cache[idx] = ct[i];
                 for(int j = 0 ; j < curSize ; j++){
                    if(j == idx) used[j] = 0;
                     else
                         used[j]++;
                }
            }
            ans += 5;
        }
    }
    return ans;
}