프로그래머스 Lv.2) 캐시

2018 KAKAO BLIND RECRUITMENT [1차]

캐시

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

풀이

LRU 부분말고는 버벅이지 않은 문제다. 오랜만에 보는 LRU 때문에 처음에 그냥 Queue에 따라서 poll하면 되겠지 하고 풀었더니 85점인가 나왔다. 그래서, LRU에 따라 제거하는 로직을 추가시켰다. 크게 어렵지 않은 문제인 것 같다.

 

로직

1. city의 정보가 담긴 String 배열을 돌면서 각각 도시를 캐시에서 체크한다.

2. 캐시에 존재하면 Cache Hit인 1을 더해주고, 존재하지 않으면 Cache Miss인 5를 더해준다.

 2-1. 캐시에 존재하면, 캐시에 들어있던 City를 현재의 인덱스로 최신화 시킨다.

3. LinkedList에 주어진 캐시 사이즈보다 많이 들어있으면 LRU에 따라 가장 쓰이지 않은 도시를 poll 해준다.

 

코드

import java.util.LinkedList;

class Solution {
    final static int CACHEHIT =1, CACHEMISS =5;
    
    public int solution(int cacheSize, String[] cities) {
        return getExecuteTime(cacheSize, cities);
    }
    
    private int getExecuteTime(int cacheSize, String[] cities) {
        int result =0;
        LinkedList<String> cache = new LinkedList<>();
        for(String city : cities) {
            String standardCity = getStandard(city);
            if(cache.contains(standardCity)) {
                result += CACHEHIT;
                for(int i=0; i<cache.size(); i++) { // LRU 부분
                    if(cache.get(i).equals(standardCity)) {
                        cache.remove(i);
                    }
                }
            } else {
                result += CACHEMISS;
            }
            cache.offer(standardCity);
            if(cache.size() > cacheSize) {
                cache.poll();
            }
        }
        return result;
    }
    
    private String getStandard(String str) {
        StringBuffer sb = new StringBuffer();
        
        for(int i=0; i<str.length(); i++) {
            char ch = str.charAt(i);
            if(ch >=97) {
                ch-=32;
            }
            sb.append(ch);
        }
        return sb.toString();
    }
}