프로그래머스_캐시_day18

알고리즘 챌린지 18일 차이다. 오늘은 Level2로 분류된 카카오 블라인드 채용 문제를 가져왔다. 
카카오 해설을 보니 난이도가 (하)로 분류되어 있지만 정답률이 약 45%였다고 한다. 이 문제를 풀기 위한 키포인트는 LRU를 구현할 수 있는가와 제약 조건(cacheSize == 0)을 제대로 이해했는가 정도가 될 것이다.

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

프로그래머스

 

주어진 상황 자체는 단순하다. 페이지 교체 알고리즘인 LRU는 캐싱 공간이 가득 찼을 경우 새로운 가장 마지막에 참조된 페이지(=데이터)를 교체하는 것이다. 페이지 교체가 일어나는 경우(cache miss), 페이지 교체가 일어나지 않는 경우 (cache hit)이며, 특수한 경우는 cacheSize가 0이라는 점이다. 이 때는 주어진 cities의 개수만큼 cache miss가 일어나기 때문에 단순히 개수 * 5를 반환해 주면 된다. 아래 코드와 주석을 살펴보면 이해가 될 것이다. 

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        if(cacheSize == 0) {
            answer = cities.length * 5;
            return answer;
        }
        
        //페이지 캐싱 자료구조
        List<String> lru = new LinkedList<>();
        for (int i=0; i<cities.length; i++) {
            String city = cities[i].toLowerCase(); //대소문자 구분 없음
            
            // cache miss
            if(!lru.contains(city)) {
                answer += 5;
                //캐싱 공간이 가득찬 경우 가장 앞(가장 마지막에 참조된)에 있는 페이지 삭제
                if(lru.size() >= cacheSize) {
                    lru.remove(0);
                }
                lru.add(city);
                continue;
            }else { 
                //cache hit
                //기존에 있는 내용을 삭제후 신규 등록하여 최근에 참조되었음을 나타낼 수 있게 한다.
                answer += 1; 
                lru.remove(city);
                lru.add(city);
            }
            
            
        }
        return answer;
    }
}