[Programmers] [1차] 캐시

// 0 <= cacheSize <= 30
// city <= 100,000 -> only Eng and need make lowercase 
// city.length <= 20
// LRU사용
// hit = 1
// miss = 5

// linkedList를 통해 캐시 구현

import java.util.HashMap;
import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();
        for(int i = 0; i < cities.length; i++){
            String key = cities[i].toLowerCase();
            int num = checkCache(cache, key);
            cache.addLast(key);
            if(num > -1){
                cache.remove(num);
                answer+=1;
            }else{
                if(cache.size() <= cacheSize){
                    answer += 5;
                }else{
                    cache.poll();
                    answer+= 5;
                }
            }
        }
        return answer;
    }
    
    public int checkCache(LinkedList<String> list, String check){
        int idx = 0;
        for(String s : list){
            if(check.equals(s))
                return idx; 
            idx++;
        }
        return -1;
    }
}