[2018 KAKAO BLIND RECRUITMENT] [1차] 캐시 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

 

[문제 간단 요약]

1. 도시 이름이 주어지고 LRU(Least Recently Used) 방식의 캐시를 구현하는 문제

• 가장 오래 전에 사용된 데이터를 가장 먼저 제거하는 캐시 교체 알고리즘
• 캐시의 크기 제한이 있을 때, 새 데이터를 넣기 위해 캐시에서 데이터를 제거해야 한다면, 가장 오래 사용되지 않은 데이터부터 제거
• 캐시에 접근(조회 또는 삽입)한 데이터는 가장 최근에 사용된 것으로 간주되어 맨 뒤로 이동

[문제 해결 방안]

1. 도시 이름을 대문자로 만들어 비교

2. 도시를 캐시 리스트로 관리하여 문제 해결

도시가 캐시에 있음	Cache Hit	+1	- 해당 도시 삭제 - 다시 맨 뒤에 추가 (가장 최근 사용)
도시가 캐시에 없음 & 캐시 공간 여유 있음 (len(cache) < cacheSize)	Cache Miss	+5	- 도시를 캐시에 추가
도시가 캐시에 없음 & 캐시 공간 가득 참 (len(cache) >= cacheSize)	Cache Miss	+5	- 맨 앞의 도시 제거 (LRU 제거) - 새 도시 추가

[문제 해결 코드 - python]

def solution(cacheSize, cities):
    answer = 0
    cache_arr = []
    if cacheSize == 0:
        return len(cities)*5
    for city in cities:
        city = city.upper()
        if city in cache_arr:
            answer+=1
            cache_arr.remove(city)
            cache_arr.append(city)
        elif len(cache_arr) < cacheSize:
            answer+=5
            cache_arr.append(city)
        else:
            answer+=5
            cache_arr.pop(0)
            cache_arr.append(city)
    return answer

 

[문제 해결 코드 - javascript]

function solution(cacheSize, cities) {
    var answer = 0;
    let cache_arr = []
    if (cacheSize === 0) {
        return cities.length * 5
    }
    for (let city of cities) {
        city = city.toUpperCase()
        if (cache_arr.includes(city)) {
            answer += 1
            cache_arr = cache_arr.filter((e) => e !== city)
            cache_arr.push(city)
        } else if (cache_arr.length < cacheSize) {
            answer += 5
            cache_arr.push(city)
        } else {
            answer += 5
            cache_arr.shift()
            cache_arr.push(city)
        }
    }
    return answer;
}