캐시

유태형·2022년 2월 15일

코딩테스트 프로그래머스

프로그래머스 - Level 2

목록 보기

17/36

문제

문제 분석

캐시 Hit와 miss를 구분하여 answer에 값을 저장하고 비교하는 문제이다. 캐시와 LRU에 대해서 사전에 알고 있어야만 문제를 풀 수 있다.

풀이

캐시

캐시는 사전에 나온 값들을 미리 저장하고 있다가 새로 들어온 값이 캐시에 있으면 hit, 없으면 miss로 구분한다.

그렇다면 캐시의 크기가 한정되어 있고 무수히 많은 값이 들어오면 어떻게 처리해야 할까?

LRU

캐시 교체 알고리즘은 중요하다. 캐시 크기가 무한정이다면 필요 없겠지만 캐시는 크기가 작고 빠르다.
캐쉬의 크기보다 많은 데이터들을 받아야 한다면, 캐쉬에 이미 있던 어떤 데이터는 삭제되어야 새로운 데이터를 저장할 수 있는건 당연하다.

문제에서도 LRU를 교체 알고리즘으로 제시하였다. 여러가지 많은 교체 알고리즘이 존재하지만 LRU는 가장 최근에 쓰인 데이터들이 캐시에 저장된다. 즉 삭제되어야 하는 상황이라면 사용된지 가장 오래된 데이터가 삭제된다.

고려해야할 점들을 확인해 보자

1.캐시 크기가 0인지
2.데이터가 hit(캐시에 존재O)인지 miss(캐시에 존재X)인지
3.캐시가 다 찼는지

		if(cacheSize == 0){ //캐시 size = 0
           answer += 5;
       }else if(cache.size() < cacheSize){ //캐쉬가 덜 찼을 때, 추가만
           if(number == -1){ //miss
               answer+=5;
           }else{ //hit
               answer+=1;
           }
       }else{ //캐쉬가 다 찼을 때, 맨앞이나 해당 요소 삭제
           if(number == -1){ //miss
               answer+=5;
               cache.remove(0);
           }else{ //hit
               answer+=1;
               cache.remove(number);
           }
       }

hit면 캐시내 해당 데이터만 마지막 사용시간을 갱신해주면 될 것이다. miss시 캐시가 다 찼으면 가장 오래된 데이터를 삭제하고 새 데이터를 추가해야한다. 반대로 덜 찼으면 추가만 하면 된다.

코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        int number;
        ArrayList<String> cache = new ArrayList<String>();
        
        for(String city:cities){
            city = city.toLowerCase();
            number = -1;
            
            for(int i=0;i<cache.size();i++){
                if(i == cacheSize) break; //캐쉬 크기 만큼 봄
                
                if(cache.get(i).equals(city)){ //hit시
                    number = i; //캐시내 번호 저장
                    break;
                }
            }
            
            if(cacheSize == 0){ //캐시 size = 0
                answer += 5;
            }else if(cache.size() < cacheSize){ //캐쉬가 덜 찼을 때, 추가만
                if(number == -1){ //miss
                    answer+=5;
                }else{ //hit
                    answer+=1;
                }
            }else{ //캐쉬가 다 찼을 때, 맨앞이나 해당 요소 삭제
                if(number == -1){ //miss
                    answer+=5;
                    cache.remove(0);
                }else{ //hit
                    answer+=1;
                    cache.remove(number);
                }
            }
            
            cache.add(city); //갱신
            
        }
        return answer;
    }
}