[프로그래머스] 캐시

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

문제에서 제시한 LRU 알고리즘을 이용하여 풀이하였습니다.

2) 알고리즘

• LRU (Least Recently Used)

3) 풀이 코드

사용 언어 - Python

from collections import deque

def solution(cacheSize, cities):
    answer = 0                          # 정답 변수
    q = deque()                         # 캐시 공간

    if not cacheSize:                   # 캐시 사이즈가 0인 경우, 입력마다 항상 5초가 소요 됨
        return len(cities) * 5

    for city in cities: 
        city = str(city).lower()        # 대소문자 구분을 안함
        if city not in q:               # 현재 도시가 캐시 공간에 저장되어 있지 않으면
            if len(q) >= cacheSize:     # 캐시 공간이 꽉 차있으면 가장 사용안한 입력 제거
                q.popleft()
            q.append(city)              # 새로운 입력 추가
            answer += 5                 # 5초 증가
        else:
            q.remove(city)              # 캐시 공간에 이미 저장되어 있다면, 기존에 저장된 위치 제거
            q.append(city)              # 가장 최근 입력으로 다시 추가
            answer += 1                 # 1초 증가

    return answer

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

LRU 알고리즘을 모르고 있어서 어려움을 겪었습니다.

2) 새롭게 학습한 내용

LRU 알고리즘을 새롭게 학습하였습니다.

• 블로그

---

🔗 문제 링크

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

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다