2018 KAKAO BLIND - 캐시

1. 문제

2018 KAKAO BLIND 캐시

2. 접근

LRU 캐시 교체 알고리즘을 구현하면 된다. 간단하게 if else문으로 구분해 주면 되는데
cache hit 라면 1만큼 시간을 더해주고, cache miss면 5만큼 시간을 더해준 뒤 사후 처리를 해주면 되는데 만약 cache 공간이 남아 있다면 그냥 추가를 해주면 되고, cache에 남은 공간이 없다면 가장 사용한 지 오래된 데이터를 바꿔주면 된다. 나는 데이터와 데이터가 들어온 순서를 같이 관리하기 위해 HashMap을 사용했다.

3. 코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int cacheSize = 3;
        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
        System.out.println(new Solution().solution(cacheSize, cities));
    }

}

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if(cacheSize==0){
            return 5*cities.length;
        }

        int answer = 0;
        HashMap<String, Integer> map = new HashMap<>();
        int idx = 0;
        for(int i=0;i<cities.length;i++){
            String str = cities[i].toLowerCase();
            if(map.containsKey(str)){ // cache hit
                map.put(str, idx);
                idx++;
                answer += 1;
            } else { // cache miss
                if(map.size()<cacheSize){ // cache 공간이 남은 경우
                    map.put(str,idx);
                    idx++;
                    answer += 5;
                } else { // cache 공간이 남지 않은 경우 LRU 실행
                    Iterator<String> it = map.keySet().iterator();
                    String removeData = "";
                    int min = Integer.MAX_VALUE;
                    while(it.hasNext()){
                        String temp = it.next();
                        // idx 값이 작을 수록 나온지 오래된 캐시 데이터
                        if(min >= map.get(temp)){
                            min = map.get(temp);
                            removeData = temp;
                        }
                    }
                    map.remove(removeData);
                    map.put(str,idx);
                    idx++;
                    answer += 5;
                }
            }
        }
        return answer;
    }
}

4. 결과

끝.