(C++) 2018 KAKAO BLIND RECRUITMENT[1차] 캐시

1. 문제

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

코딩테스트 연습 - [1차] 캐시

 

2. 풀이/설명

개념 설명

 - 캐시: 데이터를 미리 복사해둔 임시장소

 - cache hit : 새 data가 이미 캐시에 있을 때

 - cache miss : 새 data가 캐시에 없을 때 

 - LRU (Least Recently Use) : 

새로 사용하는 캐시를 맨 뒤로 넣은 후 앞에서 부터 (= 사용했었던 순서로) 제거한 후 새로운 캐시를 넣는 방법

 

예)

캐시크기가 3 

도시 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] 일때

1.

Jeju : 캐시에 없음 -> 캐시 미스 -> answer += 5

Pangyo : 캐시에 없음 -> 캐시 미스 -> answer += 5

Seoul : 캐시에 없음 -> 캐시 미스 -> answer += 5

Jeju

Pangyo

Seoul

cache full

 

2.

NewYork : 캐시에 없음 -> 캐시 미스 - > answer += 5

캐시가 꽉참 -> 제일 먼저 사용했었던 (= 제일 최근에 사용하지 않았던) Jeju 제거

캐시 앞으로 당긴 후 제일 뒤에 NewYork push

Pangyo

Seoul

Newyork

이런 식으로 반복

 

즉 알고리즘을 4개로 나눌 수 있다. 

	cache full	cache full X
cache miss	맨 앞의 원소 delete 나머지 원소 앞으로 옮기기 맨 뒤로 원소 넣기	제일 처음 빈 배열 원소 넣기
cache hit	원소 찾기 & 해당 원소 delete 나머지 원소 앞으로 옮기기 맨 뒤로 원소 넣기	원소 찾기 & 해당 원소 delete 나머지 원소 앞으로 옮기기 제일 처음 빈 배열 원소 넣기

 

3. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    if(cacheSize != 0){
    vector <string> cacheArr;
    for(int i = 0; i < cities.size();i++){
        cacheArr.push_back("0");
    }
    int hit;
    bool full;
    for(int i = 0; i < cities.size();i++){
        string new_c = (cities[i]);
        transform(new_c.begin(), new_c.end(), new_c.begin(), ::tolower);
            hit = -1;
            full = false;
            
            //miss인지 hit인지 판별
            for(int k = 0; k < cacheSize; k++){
                if(new_c == cacheArr[k]){
                    hit = k;
                    break;
                } //hit일 경우 해당 인덱스 저장
            }
            
            //full인지 아닌지 판별
            if(cacheArr[cacheSize-1] != "0"){
                full = true;
            }
            
            //full && miss
            if((full) && (hit == -1)){
                for(int k = 0 ; k < cacheSize-1; k++){
                    cacheArr[k] = cacheArr[k+1];
                }
                cacheArr[cacheSize-1] = new_c;
                answer = answer+ 5;
            }
            //full && hit
            else if(full && (hit != -1)){
                if(hit != cacheSize-1){
                for(int k = hit ; k < cacheSize-1; k++){
                    cacheArr[k] = cacheArr[k+1];
                }
                }
                cacheArr[cacheSize-1] = new_c;   
                answer +=1;
            }
            //nonfull && hit
            else if(!full && (hit != -1)){
                for(int k = hit ; k < cacheSize-1; k++){
                    cacheArr[k] = cacheArr[k+1];
                }
                for(int k = 0; k < cacheSize; k++){
                    if(cacheArr[k] == "0"){
                        cacheArr[k] = new_c;
                        break;
                    }
                }
                answer+=1;
            }
            // nonfull && miss
            else if(!full && (hit == -1)){
                for(int k = 0; k < cacheSize; k++){
                    if(cacheArr[k] == "0"){
                        cacheArr[k] = new_c;
                        break;
                    }
                }
                answer+=5;
            }
            
        }
    }
    else{
         for(int i = 0; i < cities.size();i++){
         answer += 5;
        }         
    }
    return answer;
}

 

 

4. 그외

cacheSize == 0일 수도 있다는 걸 나중에봐서

자꾸 Secument fault 가 나와서 배열 다 점검하고 주석하고 개 뻘짓을 다했는데 

문제는 cacheSize == 0일때와 아닐때를 나누지 않아서 잘못 된 거였다.

시간을 아끼고 싶다면 마음을 조급하게 굴지 말고,, 제발 문제를 잘읽자

 

그래도 오늘건 쉬워서 금방 풀어서 기분이 좋다..ㅠㅠ 흑흑

모든 문제가 이정도 난이도였으면,,,,,ㅎㅎ

 

궁금한 건 댓글 달아주세용><