프로그래머스)[1차] 캐시-python

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

LRU를 사용해 문제를 풀라는 얘기다.

 

LRU에 대한 자세한 설명은 

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)

이쪽 블로그를 참조하면 될 것이다.

처음에 작성한 코드는 무난했다.

 

def solution(cacheSize, cities):
    answer = 0
    last = 0 
    arr = []
    idx = []

    if cacheSize == 0:
        return len(cities) * 5

    for i in range(len(cities)):
        cities[i] = cities[i].lower()

        if cities[i] not in arr:
            if len(arr) < cacheSize:
                arr.append(cities[i])
                idx.append(i)
                answer += 5

            else:
                indes = idx.index(min(idx))

                idx[indes] = i
                arr[indes] = cities[i]
                answer+= 5
        else:
            indes = idx.index(min(idx))
            answer += 1
            idx[indes] = i

    return answer

다만, 테스트케이스 11, 16, 18,19,20에서 모두 실패했다.

1시간 동안 생각해도 도무지 이유가 떠오르지 않아서 처음부터 다시 작성했다.

이 코드는

인덱스에 상관하지 않고 idx리스트에 i를 넣어 항상 최신화를 유지했다.

그러나 어디선가 자꾸만 실패했다.

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

두번째로 작성한 코드는 무난하게 통과했다.

캐시사이즈가 0인 경우를 제외하고 

city가 arr에 없을 경우부터 생각해보자.

city가 arr에 없을 경우는 두 개다.

캐시 사이즈가 모두 꽉차지 않았거나, 꽉 찼음에도 없는 경우.

만일 캐시사이즈가 꽉차지 않았을 경우 arr.append를 해주면 된다.

만일 캐시 사이즈가 꽉 찼음에도 arr안에 없을 경우 0번째를 pop하고 append시켜주었다.

그리고 이 두가지. 경우 모두 hit가 아니므로 answer += 5

 

이제 남은 경우는 city가 arr에 있을 경우다.

이경우는 단순하다 꽉찼거나 꽉차지 않았거나 상관하지 않고 city의 index번째를 pop.

즉 arr = [1,2,3], city= 2 인 경우, arr[1]번째를 pop해준 뒤, append시켜준다.

 

문제 자체는 그다지 어렵지 않다.

LRU에 대한 지식이 없을 경우에도 간단한 검색만으로도 쉽게 이해할 수 있다.

단지 구현이 어렵다는게 흠이었다.