[2017 카카오 코딩테스트] 캐시

분류 

시뮬레이션

 

요구사항

캐시를 이용하여 캐시 비용 구하기

 

풀이

운영체제 공부하면서 배웠던 캐시이다

캐시 크기가 작아 기존에 있는 데이터를 찾을때 처음부터 끝까지 찾는 식으로 했다

더 쉬운 풀이가 있을 거 같다

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <deque>
#include <map>

using namespace std;

struct go{
    string str;
    int flag;
    int index;
};
int cacheSize=0;
go cache[33];
bool Find(string str){
    for(int i=0 ; i <cacheSize; i++){
        if( cache[i].str==str){
            return true;
        }
    }
    return false;
}

int Get_Index(){
    int minindex=0;
    int minvalue=987654321;
    for(int i=0 ; i <cacheSize; i++){
        if( cache[i].index < minvalue){
            minvalue=cache[i].index;
            minindex=i;
        }
    }
    return minindex;
}

int main(){
    cacheSize=3;
    int cacheIn=0;
    vector<string> city={"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};
    
    int answer=0;
    for(int i =0 ; i <city.size() ; i++){
        //있으면 넘어가고
        if(Find(city[i])){
            answer+=1;
        }
        else{
            answer+=5;
            //없으면 비어있는 공간이 있으면 비어있는 공간에 넣고
            if(cacheIn < cacheSize){
                for(int j=0 ; j <cacheSize; j ++){
                    if(cache[j].flag==0){
                        cache[j].flag=1;
                        cache[j].str=city[i];
                        cache[j].index=i;
                        cacheIn++;
                        break;
                    }
                }
            }
            else{
                //LRU로 제일 이전 인덱스 찾아서 그놈이랑 교환
                int Find_index=Get_Index();
                //업데이트 해주기
                cache[Find_index].flag=1;
                cache[Find_index].str=city[i];
                cache[Find_index].index=i;
            }
        }
    }
    cout<<answer<<endl; 
}