[프로그래머스] LV2 캐시

junah201·2022년 8월 27일
0

알고리즘

목록 보기
1/6

문제 제목 : [1차] 캐시
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17680
문제 출처 : 2018 KAKAO BLIND RECRUITMENT

최근에 지인의 권유로 프로그래머스를 시작했다. Lv1 코딩테스트부터 보던 중 Lv2에서 막혔던 문제가 있어서 정리해보았다.

문제 설명

입력값은 단순히 캐시의 크기와 도시의 이름들을 제공해준다.
도시에 관한 정보를 데이터베이스에서 하나씩 순차적으로 불려오는데 이 때 하나씩 불러오게되면 중복되어서 가져오는 값 때문에 조금 더 효율적으로 하기 위해서 캐싱을 해서 한번 불러온 데이터는 일정 시간동안 저장을 해둔 후 해당 도시에 데이터를 다시 불러오면 캐시에 저장된 값을 불러온다. 이때 데이터베이스에서 불러오면 소요시간은 5초이고, 캐시에서 불러오면 소요시간은 1초이다. 캐시 방식은 LRU (Least Recently Used) 방식을 사용한다...?

LRU라는 캐시방식은 처음 들어보는 캐시 방식이기 때문에 찾아보았다. (사실 캐싱 한번도 안해봤다..)

LRU (Least Recently Used)

만약 데이터가 캐시에 있으면

  1. 데이터가 캐시에 있는지 찾는다.
  2. 만약 데이터가 캐시에 있으면 해당 데이터를 사용한다.
  3. 캐시된 데이터를 가장 앞으로 이동시킨다.

만약 데이터가 캐시에 없으면

  1. 데이터가 캐시에 있는지 찾는다.
  2. 만약 데이터가 캐시에 없으면 데이터베이스에서 불러와서 사용한다.
  3. 불러온 데이터를 캐시 맨 앞에 넣어준다. (캐시 개수가 초과되었다면 가장 오래된 데이터를 삭제한다.

다음과 같은 로직을 구현하기 위해서 아래와 같이 함수를 작성했다.

def updateCache(city: str, cacheSize: int, is_exist: bool):
    global cacheCities

    if cacheSize == 0:
        return

    elif is_exist:
        cacheCities.pop(cacheCities.index(city))
    elif len(cacheCities) == cacheSize:
        cacheCities.pop(0)

    cacheCities.append(city)

자잘한 조건

  1. 도시 이름은 대소문자 구분을 하지 않는다.
  2. cacheSize는 0도 가능하다.

코드

소스 : github

profile
개발자를 꿈꾸는 사람

0개의 댓글