문제:

풀이방법:

조건에 주어진 LRU(Least Recently Used)를 사용하면 풀 수 있는 문제이다. LRU 캐시 교체 알고리즘이란 가장 오래전에 사용한 캐시는 자주 사용하지 않는다고 판단하고 새로 들어오는 캐시에게 자리를 내어준다는 알고리즘이다. 즉, 가장 오래전에 사용된 캐시를 빼버리고 새로운 값을 넣어버리면 된다. python의 list 내장 함수를 사용하면 어렵지 않게 풀 수 있다. list는 새로운 값을 넣어버리면 list의 맨 끝에 값을 넣기 때문에 자동적으로 인덱스 0번째에 있는 값이 오래된 값이다. 따라서 캐시에 없는 값이 들어오면 0번째 값을 빼고 새로운 값을 넣으면 LRU를 만족할 것이다. 그리고 만약 이미 있는 값이 들어왔다고 하더라도 remove로 값을 제거하고 새로 값을 넣어주어야 한다. 그래야 이 값의 사용시간이 최신화되기 때문이다. 각 행위마다 5초(miss)와 1초(hit)를 더한다면 답을 얻을 수 있을 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(cacheSize,cities):
    cache=[]
    answer = 0
    for city in cities:
        if city.lower() in cache:
            answer+=1
            cache.remove(city.lower())
            cache.append(city.lower())
        else:
            answer+=5
            if 0<= len(cache) < cacheSize:
                cache.append(city.lower())
            else:
                cache.append(city.lower())
                cache.pop(0)
    return answer
cs

문제링크:

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

'Algorithm > Python' 카테고리의 다른 글

[Programmers]2018 Kakao. 오픈채팅방  (0) 2019.09.29
[Programmers]2017 Kakao.비밀지도  (0) 2019.09.28
[Programmers]2017 Kakao. 뉴스 클러스터링  (0) 2019.09.26
[BOJ]1987. 알파벳  (0) 2019.09.25
[BOJ]1759. 암호 만들기  (0) 2019.09.24

+ Recent posts