[Python - Lv.2] [1차] 캐시

문제

프로그래머스

문제

문제

문제 이해

• DB 캐시를 적용할 때 캐시 크기에 따른 실행 시간 측정 프로그램 작성
• 캐시 크기 cacheSize와 도시이름 배열 cities를 입력 받음
• 캐시 교체 알고리즘은 LRU(Least Recently Used) 사용
• cache hit일 경우 실행 시간 1, cache miss일 경우 실행 시간 5
• LRU : cache miss일 경우 가장 마지막에 사용된 캐시와 교체

풀이

캐시 리스트를 활용한 LRU 알고리즘을 구현하여 cache 실행 시간을 구한다.

1. 캐시 리스트 cache, 시간 변수 time 생성 및 cities 순회(단, cacheSize가 0이면 len(cities) * 5로 바로 반환)
2. cache에 해당 city가 존재하는지 확인
3. cache hit일 경우 time 1 증가, cache miss일 경우 time 5 증가(LRU 알고리즘 활용)
4. LRU 알고리즘을 활용하여 cache 재배치

<LRU(Least Recently Used)>
cache miss일 경우 cache에서 사용한지 가장 오래된 것을 삭제, 더 자세한 정보는 (참고 링크) 확인

LRU 알고리즘은 해당 cache가 언제 사용된 것인지 인지해야 함
cache 리스트의 인덱스가 커질 수록 최근에 사용된 cache인 상태를 유지하도록 작성
1. cache hit일 경우 해당 캐시를 가장 뒤로 보냄(append, pop)
2. cache miss일 경우 cache가 꽉차지 않았다면 append, 꽉차있다면 맨 앞 캐시 pop 및 사용한 문자열 append

코드

hit일 경우 해당 city를 맨 뒤로 보내는 과정에서 pop과 index 메소드를 동시에 사용하므로 시간 복잡도가 O(n^2)가 된다. cacheSize가 최대 30으로 O(n^2)이 되더라도 시간이 오래 걸리지 않을 것이라 생각하였다. 실제로 테스트에서도 빠른 속도로 실행되는 것을 확인할 수 있다.

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

    return time

테스트 결과

참고 링크

LRU(Least Recentyl Used) 알고리즘 이란

https://velog.io/@ddyy094/LRULeast-Recently-Used-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%9E%80

 

[Python] 리스트 주요 연산 시간 복잡도

https://velog.io/@eastgloss0330/%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EC%A3%BC%EC%9A%94-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84