프로그래머스 Level2 2018 카카오 [1차] 캐시 Python

문제 링크

풀이

LRU 알고리즘을 사용하요 캐싱을 구현하는 간단한 문제이다.

deque를 사용하면 편하게 구현이 가능했지만

LFU 알고리즘을 생각하고 구현을 해버렸다...

dic 에는 마지막에 참조되었던 번호를 넣어준다.

캐시가 꽉 찼을때 dic안에 있는 마지막 참조된 인덱스를 기준으로 정렬을해서 0번째를 교체하는 방식으로 했다.

 

제한사항

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

 

정답 코드

def solution(cacheSize, cities):
    answer = 0
    dic = {}
    cache = []
    for i in range(len(cities)):
        city = cities[i].lower()
        if city in cache :
            answer+=1
            dic[city] = i
        else:
            answer+=5
            dic[city] = i
            if len(cache) < cacheSize:
                cache.append(city)
            elif cacheSize != 0:
                cache.sort(key= lambda x:dic[x])
                if dic[cache[0]] < dic[city]:
                    cache[0] = city
    return answer

 

풀이 설명

예외처리는 소문자 , 대문자를 구별하지 않고 cacheSize가 0 일대를 고려해야한다.