[프로그래머스] 캐시

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

 

 

 

** Python

 

from collections import deque
CACHE_HIT = 1
CACHE_MISS = 5
def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * CACHE_MISS
    answer = 0
    q = deque()
    for city in cities:
        _city = city.lower()
        if _city in q:
            answer += CACHE_HIT
            index = q.index(_city)
            del q[index]
            q.appendleft(_city)
        else:
            if len(q) == cacheSize:
                q.pop()
            q.appendleft(_city)
            answer += CACHE_MISS
    return answer

 

 

추천 1등 풀이. deque 메소드를 기본으로 알아둬야 겠다.

 

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time

 

 

참고: https://velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BA%90%EC%8B%9C-Java

import java.util.*;

class Solution {
    
    static final int CACHE_HIT = 1;
    static final int CACHE_MISS = 5;
    
    public int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0) return 5 * cities.length;
        
        int answer = 0;
        
        LinkedList<String> cache = new LinkedList<>();
        
        for(int i = 0 ; i < cities.length ; ++i){
            String city = cities[i].toUpperCase();
            
            // cache hit
            if(cache.remove(city)){
                cache.addFirst(city);
                answer += CACHE_HIT;
            
            // cache miss
            } else {
                int currentSize = cache.size();
                
                if(currentSize == cacheSize){
                    cache.pollLast();
                }
                
                cache.addFirst(city);
                answer += CACHE_MISS;
            }
        }
        return answer;
    }
}