[프로그래머스][Level 2][Python] [1차] 캐시

밑의 링크는 프로그래머스에서의 문제 링크입니다.

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

 

 

 

 

 

 

 

 

파이썬 코드와 결과입니다.

# 캐시 크기 cacheSize, 도시 이름 리스트 cities가 매개변수로 주어집니다.
def solution(cacheSize, cities):
    # 총 실행시간을 저장할 변수를 선언합니다.
    time = 0

    # cacheSize가 0인 경우
    if cacheSize == 0:
        # 총 실행시간은 cities의 길이에 cache miss인 경우의 실행시간 5를 곱한 값입니다.
        time = len(cities) * 5
    # cacheSize가 0이 아닌 경우
    else:
        # cities에 있는 모든 도시 이름들을 소문자로 처리해줍니다.
        cities = list(map(lambda city: city.lower(), cities))
        # cache를 하나 만들어줍니다.
        # 리스트 변수로 선언합니다.
        cache = []

        # cities에 있는 도시 하나마다 반복해봅니다.
        for city in cities:
            # 현재 도시가 cache에 들어있지 않다면
            if city not in cache:
                # cache에 현재 도시를 넣어줍니다.
                cache.append(city)
                # cache miss이므로 총 실행시간에 5를 더해줍니다.
                time += 5

                # 현재 도시를 넣고 난 뒤 cache의 길이가 cacheSize 보다 크다면
                if len(cache) > cacheSize:
                    # cache의 맨 앞에 있는 도시를 삭제해줍니다.
                    del cache[0]
            # 현재 도시가 cache에 들어있다면
            elif city in cache:
                # cache에 있는 현재 도시의 인덱스를 저장하는 변수를 선언합니다.
                city_idx = cache.index(city)
                # cache에 있는 현재 도시를 없애줍니다.
                cache.pop(city_idx)
                # 현재 도시를 cache의 끝에 다시 넣어줍니다.
                cache.append(city)
                # cache hit이므로 총 실행시간에 1을 더해줍니다.
                time += 1

    # 총 실행시간을 반환합니다.
    return time

결과

 

이 문제를 처음 봤을 때 '캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다'라고 나와있길래

'들어는 본 것 같은데 뭐였더라'와 '안 풀리면 따로 공부를 하고와야 풀 수 있겠네'라는 생각이 들었습니다.

 

그래도 한 번 도전은 해보자는 심정으로 LRU 옆의 괄호의 영어로 적혀있는 의미를 유추해서

코드를 짜봤는데 다행히도 통과하는 코드였습니다.

 

나중에 LRU 알고리즘에 대해서도 공부해서 포스팅해봐야겠습니다.

포스팅 할 거리가 늘어서 기분이 좋네요. ㅎㅎ

 

 

 

※ 궁금한 부분, 이상한 점 및 오타는 댓글에 부탁드립니다.

※ 더 효율적이고 빠른 정답을 환영합니다.