Lv2. [1차] 캐시

코딩테스트 연습 > 스킬트리

1. 풀이 설명

1. cacheSize 가 0인 경우에는 캐시를 사용하지 않으므로 5 * cities 의 사이즈를 반환한다.

2. cities 를 돌면서, city 를 모두 lowerCase로 변경한다 (대소문자 구분 없음)

3. city 가 cache 에 있다면 (cache hit) 으로 +1 후에 cache 의 key 값으로 city 를 value 로 idx 를 저장한다.

   • idx 는 얼마나 최근에 참조되었는지를 나타낸다.

4. city 가 cache 에 없다면, cache 사이즈를 검사하고 cache 사이즈가 casheSize 보다 작다면 cache[city] = idx 로 저장한다. 그 외 cache 가 찼다면 cache 중 가장 작은 value 값을 찾고, 가장 작은 value 값을 갖는 item을 pop 한 후에 cache[city] = idx 를 저장한다. (새로운 city 저장)

2. 나의 풀이

python

def solution(cacheSize, cities):
    answer = 0
    cache = {}
    
    if cacheSize == 0:
        return 5 * len(cities)
    
    for idx, city in enumerate(cities):
        city = city.lower()
        if city in cache:   # cache hit
            answer += 1
            cache[city] = idx
        else:               # cache miss
            answer += 5
            if len(cache) < cacheSize:
                cache[city] = idx
            else:
                least = min(cache.values())
                for key, value in cache.items() :
                    if value == least:
                        cache.pop(key)
                        cache[city] = idx
                        break
    return answer

3. 배운점

1. OS 페이지 교체 알고리즘

운영체제에서 메모리를 관리할 때, 현재 페이지 중 어떤 것과 교체할 지를 결정하는 알고리즘이다.
대표적으로 FIFO LFU LRU 등이 있다.

그 중 LRU (Least Recently Used Algorithm) 는 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다.
단점으로는 프로세스가 참조한 페이지의 시간을 기록해야하는 오버헤드 발생한다는 점이다.

2. dictionary 조회

for key, value in dictionary.items():
	print(key, value)

3. deque 의 최대 길이를 설정하여 푸는 풀이도 있다. (다른 사람 풀이 참고)

• 함수 내에서 import 문을 사용할 수 있다.
• collections.deque(maxlen=cacheSize)

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

deque(['pangyo', 'seoul', 'newyork'], maxlen=3)

인 상태에서 'LA' 차례가 된다면, 아래와 같이 cache 가 업데이트 된다. 

deque(['seoul', 'newyork', 'la'], maxlen=3) # 'la'가 append 되면서, 제일 앞에 있던 'pangyo'가 삭제됨.