[프로그래머스] 캐시

문제

문제

 

처음 작성한 코드

def solution(cacheSize, cities):
    from collections import deque
    answer = 0
    used = deque([])
    if cacheSize==0:
        return len(cities)*5
    cities = [value.lower() for _,value in enumerate(cities)]
    for i in cities:
        if i not in used:
            if len(used) < cacheSize:
                used.append(i)
            else:
                used.popleft()
                used.append(i)
            answer+=5
        else:
            used.remove(i)
            used.append(i)
            answer+=1
    return answer

1. cacheSize 0이면 계속 cache miss니까 예외처리 하고 시작했다.
2. 대소문자 구별하지 않으니까 다 소문자로 바꿨다.
3. i가 cache에 있으면 cache에 계속 존재하지만 가장 최근에 접근되었기 때문에 remove 후 append를 하여 최근 접근된 것을 표현했다.
4. i가 cache에 없으면 제일 오래된 [0]번째에 있는 원소를 빼고 제일 마지막에 append로 현재 i를 저장한다.

 

깨달은 점

• 잠시 잊었던 LRU 알고리즘을 다시 생각해냈다. LRU: 제일 안쓰이는 거 교체 -> 큐 사용(FIFO)
• 2단계지만 어렵지않았다. 파이썬이랑 친해지고 있는 것 같다.