39. 캐시

https://programmers.co.kr/learn/courses/30/lessons/17680

[1차] 캐시
2018 KAKAO BLIND RECRUITMENT 
2474명 완료

코딩테스트 연습 - [1차] 캐시

 

파이썬

비 전공자라 LRU 캐시를 처음 들어봤습니다. 
구현은 어렵지 않습니다.

deque 미사용. 

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5
    time = 0
    cache = []
    for city in cities:
        city = city.upper()
        if city not in cache:
            time += 5
            if len(cache) >= cacheSize:
                cache.pop(0)
        else:
            time += 1
            cache.remove(city)
        cache.append(city)
    return time

캐시 크기가 0일 때를 처리해야 합니다. 
간단하게 코딩하기 위해
deque를 사용하지 않았습니다만, 
간단하지 않았습니다. 

deque를 쓰는 것이 좋을 것 같습니다.

 

deque 사용. 

def solution(cache_size, cities):
    from collections import deque

    time = 0
    cache = deque(maxlen=cache_size)
    for city in cities:
        city = city.upper()
        if city not in cache:
            time += 5
        else:
            time += 1
            cache.remove(city)
        cache.append(city)
    return time

 

 

파이썬에는 데코레이터를 통해 LRU 캐시를 사용할 수 있습니다. 
https://docs.python.org/3.10/library/functools.html#functools.lru_cache

def solution(cache_size, cities):
    from functools import lru_cache

    @lru_cache(maxsize=cache_size)
    def time_test(city_):
        return city_

    for city in cities:
        time_test(city.upper())
    result = time_test.cache_info()
    return result.hits * 1 + result.misses * 5

코드 테스트에 이걸 쓰면 반칙일까요?

 

더 좋은 코드

def solution(cache_size, cities):
    from functools import lru_cache

    cash_hit_second = 1
    cash_miss_second = 5

    @lru_cache(maxsize=cache_size)
    def time_test(city_):
        return city_

    for city in cities:
        time_test(city.upper())
    result = time_test.cache_info()
    return result.hits * cash_hit_second + result.misses * cash_miss_second

 

나쁜 코드:
억지스럽게 줄여보기 --;

def solution(cache_size, cities):
    from functools import lru_cache

    @lru_cache(maxsize=cache_size)
    def time_test(city_):
        return city_

    _ = [time_test(city.upper()) for city in cities]
    return time_test.cache_info().hits * 1 + time_test.cache_info().misses * 5

 

자바

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    final int cache_hit = 1;
    final int cache_miss = 5;

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

        int time = 0;
        Queue<String> cache = new LinkedList<>();

        for (var city : cities) {
            city = city.toUpperCase();
            if (cache.contains(city)) {
                time += cache_hit;
                cache.remove(city);
            } else {
                time += cache_miss;
                if (cache.size() >= cacheSize)
                    cache.poll();
            }
            cache.offer(city);
        }
        return time;
    }
}