프로그래머스 / 해시 / [1차] 캐시

문제

---

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

프로그래머스

 

입출력

---

 

해설

---

LRU 알고리즘을 구현할 수 있는가에 대한 문제였다.

 

캐시크기가 주여지며 해당 크기까지만 캐시를 저장할 수 있다.

 

LRU알고리즘은 단순하게 설명하자면 제일 오래된 값을 버리고 새로운 값을 저장하는 방식의 알고리즘이다.

그렇기 때문에 저장할 때 들어온 순서인 index를 저장하려고 했다.

 

python의 dict를 이용하여 city : index를 유지하였고, 캐시 크기를 벗어나지 않게끔 해주었다.

 

정답코드

---

'''
'25. 09. 04

1. LRU 알고리즘.
2. hit일 때는 1, miss 5


5, 10, 15, 20, 25, 30, 35, 40, 45, 50

5, 10, 15, 16, 17, 18, 19, 20, 21

5, 10, 15, 20, 25, 30, 35, 40, 45, 50,
'''
def solution(cacheSize, cities):
    lru = {}
    
    answer = 0
    for idx, value in enumerate(cities):
        value = value.lower()
        if value in lru:#cacheHit
            answer += 1
        else:#cacheMiss
            answer += 5
            #가장 오래된 idx 삭제
        lru[value] = idx
        
        if len(lru) > cacheSize:
            target_key, target_value = '', 0x3f3f3f3f
            for key, data in lru.items():
                if data < target_value:
                    target_value = data
                    target_key = key
            del lru[target_key]
    return answer

 

깃허브 : https://buly.kr/DlK0f43

유튜브 :