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

문제

프로그래머스 - 캐시

문제 이해

• 캐시 교체 알고리즘: LRU(Least Recently Used)
  • 가장 오래된 페이지를 교체하는 알고리즘
  • 자료구조의 큐와 같이 선입선출 형태
  1. 새로운 데이터가 들어온 경우
     • 캐시에 넣어준다.
     • 캐시가 가득차있다면, 가장 오래된 데이터를 제거하고 넣어준다.
  2. 존재하는 데이터가 들어온 경우
     • 해당 데이터를 꺼낸 뒤
     • 가장 최근 데이터 위치로 보내준다.
• cache hit: 참고하고자 하는 메모리가 캐시에 존재하는 경우
• cache miss: 참고하고자 하는 메모리가 캐시에 존재하지 않는 경우

해결 과정

• cache 빈 배열을 만든다.
• .lower() : city는 대소문자를 구별하지않으므로 for문을 돌며 cache배열에 접근할 때 모두 소문자로 변경하여 저장한다.
• cacheSize가 0인 경우 cache 저장 불가능 -> cache miss -> time += 5
• cacheSize가 0이 아닌 경우 cache에 데이터가 있는지 확인
  • 이미 있으면 = cache hit -> 해당 데이터를 빼주고 최근 위치(뒤)에 넣어준다. -> time += 1
  • 없으면 = cache miss -> cache의 사이즈를 비교 -> time += 5
    • cacheSize와 cache의 길이가 같으면 가장 오래된 데이터를 빼주고 새로 넣는다.
    • 길이가 작으면 바로 넣는다.

풀이

def solution(cacheSize, cities):
    time = 0
    cache = []
    for i in cities:
        i = i.lower()
        if cacheSize != 0:
            if i not in cache:
                if len(cache) == cacheSize:
                    cache.pop(0)    
                cache.append(i)
                time += 5
            else:
                cache.pop(cache.index(i))
                cache.append(i)
                time += 1
        else:
            time += 5
            
    return time