프로그래머스 > [1차] 캐시 (Python3)

1. 문제 설명

지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.

이때, 데이터베이스에 캐시를 적용하여 성능 개선을 시도하고 있지만, 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하라.

 

 

2. 입력 형식

- 캐시 크기 (cacheSize)와 도시이름 배열 (cities)을 입력받는다.

- cacheSize는 수이며, 범위는 0  ≦ cacheSize ≦ 30 이다.

- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다.

 

 

3. 출력 형식

- 입력된 도시 이름 배열을 순서대로 처리할 때, '총 실행시간'을 출력한다.

 

 

4. 조건

- 캐시 교체 알고리즘은 LRU (Least Recently Used)를 사용한다.

- Cache hit일 경우 실행시간은 1이다.

- Cache miss일 경우 실행시간은 5이다.

 

 

5. 코드

def solution(cacheSize, cities):
	# 대소문자 구별하지 않도록 소문자로 만들어주기
    cities = [c.lower() for c in cities]
    
    # 캐시 사이즈가 0인 경우 전부 Cache miss로 간주
    if cacheSize == 0:
        return len(cities) * 5
    
    # { 도시 이름 : 참조 시간 } 저장할 딕셔너리 선언
    cache = dict()
    total = 0
	
    
    for c in cities:
        if len(cache) < cacheSize:
            if c not in cache.keys():
                total += 5
            else:
                total += 1
        else:
            if c not in cache.keys():
                total += 5
                
                # 가장 value가 큰 요소를 제거
                max_time = -1
                max_key = c
                for city, time in cache.items():
                    if max_time < time:
                        max_key = city
                        max_time = time

                del cache[max_key]

            else:
                total += 1
        
        # 공통적으로 c 아닌 도시들에 +1, c 도시에 0 부여
        cache = { city : time+1 for city, time in cache.items()}
        cache[c] = 0
        
    return total

 

 

6. 해설

https://tech.kakao.com/posts/344

카카오 신입 공채 1차 코딩 테스트 문제 해설 - tech.kakao.com

카카오 기술 블로그에 나와있는 예시 설명이다.

 

놓칠 수 있는 포인트가

1. 대소문자 구별하지 않는다는 점 : lower case로 다 변환해주기

2. cacheSize로 0이 들어올 수 있다는 점 : 전부 cache miss로 간주하여 도시 개수 * 5 해주기

3. 단순히 가장 예전에 cache에 들어왔다고 해서 cache에서 제거해야 할 대상은 아니라는 점 : '참조 시간'의 문제임

 

 

캐시에 cacheSize만큼 저장되지 않은 경우,

중복 체크만 해주고 이미 있는 도시에 대해 value + 1, 새로 들어온 도시에 대해 0으로 만들어 준다.

 

캐시에 cacheSize만큼 저장되어 있는 경우에는,

가장 참조 시간이 긴 도시를 제거하고 새로 들어온 도시를 참조시간 0으로 하여 추가해준다. 역시 이미 있는 도시에 대해서는 value + 1을 해준다.