[알고리즘] 2018 KAKAO BLIND RECRUITMENT - [JavaScript] 캐시

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

프로그래머스

본 포스팅에서 다루는 문제는 위 프로그래머스 링크를 통하여 문제 확인 및 풀이가 가능합니다!

 

1. 정답 코드

 

function solution(cacheSize, cities) {
    var answer = 0;
    let cacheList = [];
    
    if (cacheSize === 0) // 캐시 사이즈가 없는 경우 -> 모든 경우에서 cache miss
        return answer = cities.length * 5;
    
    
    for (let city of cities) {
        city = city.toUpperCase();
        if (cacheList.includes(city)) { // cache hit
            const index = cacheList.indexOf(city); // 기존 캐싱된 city 위치 확인
            cacheList.splice(index, 1); // 기존 캐싱된 city 제거
            answer++; // cache hit 시의 실행 시간
        } else { // cache miss
            if (cacheList.length === cacheSize) { // cacheSize를 모두 사용하는 경우 
                cacheList.shift(); // shift()를 사용하여 배열의 첫 번째 요소 제거
            }
            answer += 5; // cache miss 시의 실행 시간
        }
        cacheList.push(city); // 캐싱 업데이트
    }

    return answer;
}

 

2. 문제 풀이

 본 문제에서는 입력 값에 대한 '경계값 처리'와 문제 조건을 정확하게 이해하는 것이 키 포인트입니다.

입력 형식
- 캐시 크기(cacheSize)와 도시이름 배열(cities)를 입력받는다.
- cacheSize는 정수이며, 범위는 0 <= cacheSize <= 30이다.
- cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
- 각 도시의 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

조건
- 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
- cache hit 일 경우 실행시간은 1이다.
- cache miss일 경우 실행시간은 5이다.

 

  하이트라이트 처리를 한 부분은 제가 코드를 작성하면서 놓쳤던 부분들 혹은 제가 생각하기에 중요한 부분입니다. 하나씩 코드를 통하여 살펴보도록 하겠습니다.

 

2-1. 0 <= cacheSize <= 30이다.

 cacheSize의 경계값 중에서 0에 대한 처리를 하지 않아서 90.0/100.0 점을 획득하는 경우를 흔하게 찾아볼 수 있었습니다. 캐시 크기가 0인 경우에는 모든 도시이름에 대하여 cache miss가 발생하므로 (도시 이름 배열의 길이 * cache miss일 경우의 실행시간)에 해당하는 cities.length * 5 를 answer에 할당한 뒤 return 해주었습니다.

 

2-2. 각 도시의 이름은 대소문자 구분을 하지 않는다.

 도시의 이름은 대소문자 구분을 하지 않기 때문에 'NewYork'과 'newyork'은 같은 도시 이름으로 취급됩니다. 이를 위하여 캐시 배열에 저장하기 이전에 추가적인 처리를 하는 것이 중요합니다.

 본 코드에서는 cities 배열에 대한 반복문을 실행하면서 가져오는 city를 toUpperCase 메소드를 사용하여 모든 문자를 대문자로 변환한 뒤 배열에 저장하였습니다.

 

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

 본 문제에서 캐시 교체 알고리즘으로 LRU를 사용한다고 하였는데 LRU가 무엇인지 모른다면 문제 풀이에서 큰 어려움을 겪었을 것이라 생각됩니다. 페이지 교체 알고리즘 중 하나로 Least Recently Used(최근에 적게 사용된, 가장 오랫동안 참조되지 않은) 페이지를 교체하는 알고리즘입니다.

 즉, 캐시 메모리가 부족한 경우에는 캐싱된 이후로 가장 오랫동안 cache hit이 되지 않은 캐시를 교체해야 한다는 뜻입니다. 실제 LRU 알고리즘에서는 접근 시간도 함께 기록하지만 이번 문제 풀이에서는 cache hit이 될 때에는 기존 캐시 리스트에서 제거한 뒤 다시 추가하는 방식을 사용하였습니다.

 이를 통하여 배열의 첫 원소에는 가장 오래 전에 캐싱되거나 cache hit 되었던 city가 존재할 것이고, 마지막 원소에는 가장 최근에 캐싱되거나 cache hit 되었던 city가 존재할 것입니다. 문제 풀이 과정에서도 cache hit이 되었을 때, cache list 갱신 방법이 가장 중요합니다.

 

 

3. 마치며...

 문제 자체의 난이도는 카카오에서도 공식적으로 '하'로 지정한 만큼 어렵지는 않지만 입력 형식에 대한 경계값 처리 및 조건을 정확하게 확인하는 것이 중요한 문제였습니다. 또한, JavaScript를 사용하는 경우에는 배열의 첫 번째 원소(cacheSize가 가득 찬 경우에 이용), 특정 값(cache hit이 되어 기존 city를 제거할 때 이용)을 remove하는 방법을 명확히 알고 있지 않은 경우에는 문제 풀이에 다소 어려움을 겪을 수 있을 것이라 생각됩니다.

 

 본 문제 풀이에서 첫 번째 원소를 지우는 방법으로는 shift()를, 특정 값을 지우는 방법으로는 indexOf()를 사용하여 index를 확인한 뒤 splice(index, 1)를 사용하였습니다.