2018 카카오 BLIND RECRUITMENT 캐시

문제 유형

캐시 정말 캐시

작성 코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        // Cache Algorithm -> LRU
        Deque<String> cacheLRU = new LinkedList<>();
        for (int i = 0; i < cities.length; i++) {
            String city = cities[i].toLowerCase();
            if (cacheLRU.size() != 0) {
                if (cacheLRU.contains(city)) {
                    // hit
                    cacheLRU.remove(city);
                    cacheLRU.addLast(city);
                    answer += 1;
                } else {
                    // miss
                    cacheLRU.addLast(city);
                    answer += 5;
                }
            } else {
                cacheLRU.addLast(city);
                answer+=5;
            }
            
            if (cacheLRU.size() > cacheSize) {
                cacheLRU.pollFirst();
            }
        }
        if (cacheSize == 0) answer = cities.length*5;
        return answer;
    }
}

접근 방식

1. 기본적으로 캐시라고 대놓고 써있어서 Deque를 활용하기로 했다. 

2. LRU의 경우 만약 cache hit이 발생했을 경우 해당 내용을 가장 뒤로 보내기 때문에 해당 내용에 맞춰 코드를 작성하였다.

    - cache hit의 경우: cache에 해당 도시를 지운뒤 가장 뒤에 추가하였다.

    - cache miss의 경우: cahce에 현재 도시를 추가했다.

3. cache의 사이즈가 정해져 있기 때문에 마지막 부분에 cache 사이즈를 확인하고 만약 사이즈보다 클시에는 cache에 가장 앞에 있는 도시를 삭제했다.

개선 사항

1. 개선사항이기보다는 과거에 있었던 문제가 그대로 발생했다. 처음에 Lower Case와 Upper Case를 구분하지 않는다 부분을 읽지 않아 또 문제를 틀렸었다. 이부분은 특히, 아는 형태의 문제에서 가장 많이 발생하는 듯하다.