[알고리즘] 2018 카카오 블라인드 - 캐시

1. 문제

 

2. 나의 풀이

LRU 알고리즘을 이해하고 있으면 쉽게 풀 수 있는 문제이다. 캐시에 있으면 answer에 1을 더해주고, cache에 없으면 cache에 넣으면서 5를 더해준다. 여기서 주의해야할 점은 캐시에 있을 경우 해당 city를 cache Deque 맨앞으로 옮겨줘야한다는 것이다. 왜냐하면 가장 최근에 사용했기 때문이다.

import java.util.*;

class Solution {

    public int solution(int cacheSize, String[] cities) {

        Deque<String> cache = new ArrayDeque<>();
        int answer = 0;

        int len = cities.length;
        for(int i=0;i<len;i++){
            cities[i] = cities[i].toLowerCase();
        }

        for(int i=0;i<len;i++){

            if(cacheSize == 0){
                answer += 5;
            } else if(cache.contains(cities[i])){
                cache.remove(cities[i]);
                cache.addFirst(cities[i]);
                answer += 1;
            } else if(!cache.contains(cities[i]) && cache.size() < cacheSize){
                answer += 5;
                cache.addFirst(cities[i]);
            } else{
                answer += 5;
                cache.removeLast();
                cache.addFirst(cities[i]);
            }

        }

        return answer;
    }

}