코딩테스트 연습 2018 KAKAO BLIND RECRUITMENT[1차] 캐시

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

프로그래머스

def solution(cacheSize, cities):
    cache = []
    answer = 0
    for i in range(len(cities)):
        cities[i] = cities[i].lower()
    
    for city in cities:
        if city in cache:
            a = cache.pop(cache.index(city))
            cache.append(a)
            answer+=1
        elif len(cache) == cacheSize:
            try:
                cache.pop(0)
                cache.append(city)
                answer+=5
            except:
                answer+=5
        else:
            cache.append(city)
            answer+=5
    
    return answer

 

캐시의 상태는 크게 4가지 경우로 나눌 수 있음.
1. 캐시가 아직 모두 비어있을 때: 미스(miss)가 발생하며, 단순히 캐시에 데이터를 추가
2. 캐시에 공간이 남아있을 때: 히트(hit)가 발생하며, 해당 데이터를 캐시의 가장 최근에 사용된 위치로 업데이트
3. 캐시가 가득 찬 상태에서 새로운 데이터가 들어올 때: 미스(miss)가 발생하며, 캐시의 가장 오래 전에 사용된 데이터를 제거하고 새로운 데이터를 추가
4. 캐시가 가득 찬 상태에서 기존 데이터가 다시 접근되는 경우: 히트(hit)가 발생하며, 해당 데이터를 캐시의 가장 최근에 사용된 위치로 업데이트

 

pop(0)을 하는 과정이 거의 배열 모든 값들이 하나씩 당겨지는 과정인지라 효율성테스트에서 통과 못할거라고 생각했는데, 의외로 잘 통과했음. 아무래도 cacheSize가 작아서 pop(0)을 해도 효율성에서 그렇게 밀리진 않는듯함. gpt는 딕셔너리로 풀었는데, gpt의 풀이도 아래 첨부하겠음.

from collections import OrderedDict

def solution(cacheSize, cities):
    cache = OrderedDict()
    total_time = 0
    
    for city in cities:
        city_lower = city.lower()  # 대소문자 구분하지 않음
        if city_lower in cache:
            # cache hit
            cache.move_to_end(city_lower)
            total_time += 1
        else:
            # cache miss
            total_time += 5
            if cacheSize > 0 and len(cache) >= cacheSize:
                # 캐시가 꽉 찼으면 가장 오래된 아이템 제거
                cache.popitem(last=False)
        cache[city_lower] = True
    
    return total_time

중간중간 오답을 내긴 했지만 효율성이 내 코드보다 2~3배 이상 향상된 모습을 보여줬다.

앞으로 dictionary를 활용해 푸는 연습을 거쳐야할듯.