문제

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

나의 코드 (답안참조)

"""
1. 아이디어

2. 시간복잡도

"""

def solution(cacheSize, cities):
    
    answer = 0
    n = len(cities)
    cache = []
    
    for i in range(n): # 대소문자 구분 안한다는 조건해결
        cities[i] = cities[i].lower()
        
    for city in cities:
        
        if city in cache: # cache hit
        	# used 되면 삭제 우선순위를 젤 뒤로 보냄
            cache.remove(city) 
            cache.append(city)
            answer += 1
        
        else: # cache miss
            cache.append(city)
            answer += 5
            
            # cache miss의 경우 값을 추가할 때 cacheSize가 초과되면 오래된 데이터는 삭제한다.
            if len(cache) == cacheSize + 1:
                cache.pop(0)
            
    return answer
    

설명

큐의 성질을 조금 섞어놓은 문제..

다시 풀이한 코드

def solution(cacheSize, cities):
    
    cache = []
    time = 0
    
    for city in cities:
        
        city = city.lower() # 대소문자 구별 안한다는 조건 해결
        
        if city in cache: # cache hit
            cache.remove(city)
            cache.append(city)
            time += 1
            
        elif city not in cache: # cache miss
            cache.append(city)
            time += 5
            
            if len(cache) == cacheSize + 1:
                cache.pop(0)
        
    return time

또 다시 풀이한 코드

def solution(cacheSize, cities):
    
    answer = 0
    cache = []
    
    if cacheSize == 0:
        return len(cities) * 5
    else:
        for city in cities:
            city = city.lower()

            if cache:
                if city in cache:
                    answer += 1
                    cache.remove(city)
                    cache.insert(0, city)
                else:
                    if len(cache) >= cacheSize:
                        cache.pop()
                    cache.insert(0, city)
                    answer += 5
            else:
                cache.append(city)
                answer += 5
        
    print(cache)
    return answer

• 이거 if cachesize == 0: 필요한 이유가
  cacheSize가 0일 때 만약 cities에 ["LA", "LA"]가 있는 경우
  cacheSize가 0이기 때문에 불러올때마다 cache miss이므로 총 10초의 시간이 걸리지만
  정의해주지 않게 되면 6초의 시간이 걸리기 때문에 틀리게 됩니다
  cacheSize가 0일 때를 예외로 정의해주시면 정답이 됩니다.
  이거 때문임

참고자료