프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 31분 소요

def solution(cacheSize, cities):
    from collections import deque

    answer = 0
    
    cache = deque([])

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

        return answer

    for city in cities:
        city = city.upper()
        if not city in cache:
            if len(cache)<cacheSize:
                cache.appendleft(city)
            else:
                cache.pop()
                cache.appendleft(city)
            answer += 5
        else:
            cache.remove(city)
            cache.appendleft(city)
            answer += 1

    return answer   

페이지 Cache가 작동하는 'LRU' 알고리즘을 구현하는 문제입니다. 처음 보는 알고리즘 이였지만 작동방식은 간단하여 알고리즘 정의를 참고하여 어렵지 않게 해결할 수 있었습니다.

구현하는데 있어 첫번째 포인트는 입력되는 도시명들이 대소문자를 구분하지 않으므로 대문자로 통일하는 것이였고 두번째로 Cache안에 있는 도시명 일 경우 deque.remove로 해당 도시명을 지우고 appendleft 방금 입력된 도시명으로 만드는 것이었습니다.🦩🦩🦩

[다른 사람의 풀이1]

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

'나의 풀이'와 유사한 방식이되, deque의 최대크기를 CacheSize로 정의하여 Cache가 꽉찼을 때의 경우를 고려하지 않아도 되는 간결한 풀이었습니다.🐳🐳🐳

[다른 사람의 풀이2]

def solution(cacheSize, cities):
    # Least recently used 캐시를 모방하는 자료구조를 구현한 뒤,
    # 시뮬레이션 하는 문제.
    # 자료구조에 대해서는
    # Cache hit, cache miss 두 가지 상황만 생각하면 된다.
    # cache hit이면, 해당 데이터가 최근에 hit 되었음을 업데이트 해주고,
    # cache miss이면, 가장 오래된 데이터를 제거 후 새로운 데이터를 캐시에 추가
    # 
    # 캐시 크기는 일정하므로, O(n) search를 허용해도 될 듯. 리스트로 쉽게 가자.
    # 
    cache, answer = [], 0
    for city in [c.lower() for c in cities]:
        # cache hit인 상황.
        if city in cache and cacheSize > 0: # cacheSize가 0일수도 있음에 주의!
            answer += 1
            # 비효율적이긴 한데, 이러면 쉽게 구현할 수 있다.
            cache.remove(city)
            cache.append(city)
        # 이하는 cache miss인 상황.
        elif len(cache) < cacheSize:
            answer += 5
            cache.append(city)
        else:
            answer += 5
            cache = cache[1:]
            cache.append(city)
            
    return answer

Cache가 꽉찼을때 pop()하지 않고 슬라이싱으로 가장 오래된 도시명을 제외한 Cache 리스트로 초기화하고 새 도시명 append하는 방식이 인상깊었습니다.🐕🐕🐕

감사합니다.