[Python] 프로그래머스 Lv2_[1차] 캐시

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

프로그래머스

 

• 제한사항
  • 캐시 교체 알고리즘은 LRU(Least Recently Used) 사용
    • LRU(Least Recently Used) 알고리즘: 가장 사용한지 오래된 것을 내보내는 알고리즘
  • cache hit일 경우 실행시간은 1
    • cache hit = 이미 캐시에 있는 데이터가 다시 들어오는경우
  • cache miss일 경우 실행시간은 5
    • cache miss = 캐시에 없는 데이터가 들어오는 경우
  • 각 도시 이름은 대소문자 구분 x

 

"""
입출력 예시)

cacheSize = 3, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] -> 50
cacheSize = 3, cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"] -> 21
cacheSize = 2, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] -> 60
cacheSize = 5, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] -> 52
cacheSize = 2, cities = ["Jeju", "Pangyo", "NewYork", "newyork"] -> 16
cacheSize = 0, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"] -> 25
"""

def solution(cacheSize, cities):
    answer = 0 # 실행시간
    i = 0 # 초기 캐시 인덱스
    cache = [] 

    if cacheSize == 0: # 캐시 사이즈가 0인 경우
      return len(cities)*5 # cache miss이므로 실행시간: len(cities)*5
    
    for c in cities:
      city = c.lower() # 도시 이름은 대소문자를 구분하지 않으므로 소문자로 통일

      # city가 이미 캐시 메모리에 있는 경우
      if city in cache: 
        cache.remove(city) # 캐시에서 해당 city 위치 변경
        cache.append(city)
        answer += 1 # cache hit -> 1
      
      # city가 캐시 메모리에 없는 경우
      else:
        answer += 5 # cache miss -> 5
        # 캐시에 빈 공간이 있는 경우(캐시의 인덱스가 캐시 사이즈보다 작을 때)
        if i < cacheSize:
          cache.append(city) # city를 캐시에 보관
          i += 1 # 인덱스 + 1
        # 캐시에 빈 공간이 없는 경우
        else:
          cache.pop(0) # 캐시에서 사용된지 오래된 city 빼기
          cache.append(city) # 현재 city를 캐시에 보관

    return answer

 

 

• 다른 풀이 -> 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://dev-note-97.tistory.com/104

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

 

https://dailylifeofdeveloper.tistory.com/355

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법

 

https://ljhyunstory.tistory.com/28

코딩테스트--[1차] 캐시(프로그래머스 / 파이썬)