[/ 프로그래머스] 17680번 : [1차] 캐시

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

 

처음 문제 보고 이게 무슨 얘기인가 싶었다 

cacheSize는 데이터를 저장할 수 있는 크기이고, 

cache hit은 cpu가 참조하고자 하는 메모리가 캐시에 존재하는 경우

cache miss는 cpu가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우를 

의미한다 

 

*LRU : 가장 오랫동안 참조되지 않은 데이터를 제거한다 

캐시가 LRU로 진행하기 때문에 제일 먼저 들어간 데이터가 가장 오래되었을 것이므로, 가장 먼저 나와야한다

 

주의해야할 게 Newyork과 newyork이 같은 취급을 받기 때문에 도시 이름들을 모두 소문자화 해야한다는 것이다. 

 

- 정답 풀이 :

cacheSize가 0이라면 모든 데이터들은 5의 시간으로 데이터 처리가 되므로 도시 갯수 * 5를 해주면 된다 

 

city들을 모두 소문자로 바꾼다음에 cache에 있는 도시라면 time += 1하고 기존에 있던 city를 cache에서 제거한 후 새로운 도시를 추가해준다  

 

city가 cache에 없다면 time += 5를 해주고 이미 cache가 cacheSize만큼 데이터를 가지고 있다면 왼쪽 값을 빼주고

해당 도시를 cache에 추가해준다

 

from collections import deque

def solution(cacheSize, cities):
    time = 0
    cache = deque()
    
    if cacheSize == 0:
        return len(cities) * 5
    
    for city in cities:
        city = city.lower()
        if city in cache:
            time += 1
            cache.remove(city)
        else:
            time += 5
            if len(cache) >= cacheSize:
                cache.popleft()
        cache.append(city)
        
    return time

 

 

- 시도해 본 풀이 

50 퍼센트에서 막혔다

쓸데없이 복잡하게 풀었다

모든 도시들 소문자로 변경하기, 초기 cache 세팅하기

city들 dictionary 설정하기 

흠,,,

def solution(cacheSize, cities):
    dic = {}
    cache = []
    
     #모든 도시 이름 소문자로 바꾸기 
    for i in range(len(cities)):
        cities[i] = cities[i].lower()
        
    time = 0
    for i in range(cacheSize):
        cache.append(cities[i])
        dic[cities[i]] = 1
        time += 5
    cities = cities[cacheSize : ]
    
    for city in cities:
        if city in cache : 
            dic[city] += 1 #사용횟수 하나 증가 
            time += 1
        #캐시에 없는 경우 lru로 최근에 사용되지 않은 거 없애고 재료 추가 
        elif city not in cache: 
            temp = sorted(dic.items(), key = lambda x : x[1])
            if len(temp) > 0:
                find = temp[0][0]
                cache.remove(temp[0][0])
                del dic[find]
            
            dic[city] = 1
            cache.append(city)
            time += 5
            
    return time