캐시 (Level 2)

문제

 

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

프로그래머스

 

내 풀이

 

코드를 좀 더 줄여서 예쁘게 만들 수 있었다. 그러나 문제를 문자 그대로 구현하면 아래의 코드와 같이 되기 때문에, 다시 바꾸지 않았다.

 

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

 

 

다른 풀이

 

deque의 maxlen을 사용하여 최대 리스트의 길이를 cacheSize로 제한하였다.

그래서 만약 deque의 오른쪽에 새로운 원소가 추가되면, 자동으로 deque의 제일 왼쪽 원소가 빠지게 된다.

파이썬 라이브러리의 세계란 보면 볼수록 놀랍다.

 

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time

 

 

과거의 내 풀이

 

수치플 끝판왕

 

def solution(cacheSize, cities):
    ans = 0
    buffer = []
    if cacheSize == 0:
        return len(cities) * 5
    else:
        for city in cities:
            city = city.lower()
            # buffer의 크기가 cachesize보다 작으면
            if len(buffer) < cacheSize:
                # 이미 city가 버퍼에 있으면
                if city in buffer:
                    # 버퍼에서 그 city의 위치를 맨 뒤로 바꾸기 -> hit
                    buffer.remove(city)
                    buffer.append(city)
                    ans += 1
                # 그렇지 않으면
                else:
                    # buffer에 넣기 -> miss
                    buffer.append(city)
                    ans += 5
                continue
            # buffer의 크기가 cachesize와 같으면
            if len(buffer) == cacheSize:
                # 이미 city가 버퍼에 있으면
                if city in buffer:
                    # 버퍼에서 그 city의 위치를 맨 뒤로 바꾸기 -> hit
                    buffer.remove(city)
                    buffer.append(city)
                    ans += 1
                # 그렇지 않으면
                else:
                    # buffer의 맨 앞에 숫자 빼고, buffer 뒤에 city append하기 -> miss
                    buffer.pop(0)
                    buffer.append(city)
                    ans += 5
    return ans

 

총평

처음에 LRU를 구현 할 때, cache hit이 되었으면 hit이 된 도시는 cache의 제일 오른쪽으로 자리를 옮겨주어야 한다는 사실을 간과하였다. 이것을 고치니 바로 통과가 되었다.