[프로그래머스] 파이썬 _ 캐시 (카카오 2018)

https://programmers.co.kr/learn/courses/30/lessons/17680?language=python3#

코딩테스트 연습 - [1차] 캐시

문제유형 : 구현

 

문제풀이 : 

• LRU 알고리즘에 대해서 알고 있어야하는듯..?
• LRU알고리즘의 구현에서 가장 최근에 사용된것은 맨 뒤로 빼와서 가장 나중에 삭제되도록 하는것이다.
• 캐시히트가 일어났을대는 해당 값을 맨뒤로 빼와서 최근에 사용되었다는것을 반영시키도록하고, 캐시미스가 일어났으면 맨앞의 값을 삭제하고 새로운 값을 뒤에 추가한다.
• 큐로 구현할수도 있었는데 파이썬 deque라이브러리의경우 중간값을 pop하는 연산이 지원되지 않아 그냥 리스트로 구현했다. 시간초과 안났다. 

 

정답코드 : 

def solution(cacheSize, cities):
    # 캐시크기만큼 캐시배열을 만든다.
    # 캐시히트가 일어난경우 - 해당값을 맨뒤로 빼온다. 
    # 캐시미스가 일어난경우
    # 1. 캐시에 자리가 있는경우 - 현재값을 추가한다.
    # 2. 캐시에 자리가 없는경우 - 맨앞의 값을 없앤다음 현재값을 추가한다.
        
    
    q = []
    time = 0
    if cacheSize == 0:
        return 5 * len(cities)
    
    for c in cities:
        c = c.lower()
        if c in q:
            i = q.index(c)
            curr = q.pop(i)
            q.append(curr)
            time += 1
        else:
            if len(q) < cacheSize:
                q.append(c)
                time += 5
            else:
                q.pop(0)
                q.append(c)
                time += 5

    
    #print(q)
    return time