[JS] 프로그래머스 코딩테스트 연습 | L2 [1차] 캐시 feat 페이지 교체 알고리즘

1. 문제 설명

캐시
지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

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

출력 형식

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

조건

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

2. 입출력 예제

캐시크기(cacheSize)	도시이름(cities)	실행시간
3	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	50
3	["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]	21
2	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	60
5	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	52
2	["Jeju", "Pangyo", "NewYork", "newyork"]	16
0	["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	25

풀이 전 먼저 페이지 교체 알고리즘을 알아보았다
참조 링크 https://gomguard.tistory.com/115

페이지 교체 알고리즘

페이지

• 일반적으로 컴퓨터는 주기억 장치 램과 보조기억 장치 하드 또는 ssd를 가짐

• 운영체제는 주기억 장치보다 더 큰 용량의 프로그램을 실행하기 위해 일부만 주기억 장치에 적재해 사용

• 주기억 장치의 속도가 빠르기 때문에 보조 기억장치로부터 데이터를 램에 저장, 램에 있는 데이터로 빠르게 연산함

• 이때 램을 같은 크기 블록으로 구성해 운용하는데 이 블록이 바로 페이지

cache hit

: CPU가 계산할 때 필요한 데이터가 페이지에 있음

cache miss

: CPU가 계산할 때 필요한 데이터가 페이지에 없음 → 보조기억장치로부터 데이터를 페이지로 옮겨온 후 계산

당연히 cache miss일 때 시간이 더 오래걸림
따라서 빠른 연산을 위해 체이지 여러 정보 중 어떤 정보를 오래 저장해 놓아야하는지가 매우 중요
램 자원이 같더라도 어떤 방식의 알고리즘을 사용하느냐에 따라 연산시간이 상이하기 때문

LRU 알고리즘

: Least Recently Used Algorithm
가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘
페이징 기법으로 메모리를 관리하는 운영체제에서 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느것과 교체할지 결정하는 방법

문제풀이

function solution(cacheSize, cities) {
  let answer = 0;
  let cache = [];
  const len = cities.length;

  // 캐시 사이즈가 0이면 모든 도시에 대해 캐시 미스
  if (cacheSize === 0) return len * 5;

  for (let i = 0; i < len; i++) {
    // test case 5
    const city = cities[i].toLowerCase();
    const index = cache.indexOf(city);

    // cache 배열에 city가 있을 때 (cache hit)
    if (cache.indexOf(city) !== -1) {
      answer += 1;
      cache.splice(index, 1);
      cache.push(city);
    }
    // cache 배열에 city가 없을 때 (cache miss)
    else {
      answer += 5;
      // 캐시 배열에 다 차면 cache[0]을 없애줌
      if (cache.length === cacheSize) cache.shift();
      cache.push(city);
    }
  }

  return answer;
}

캐시 배열을 만들고 배열에 같은 도시가 있으면 answer +1, 기존 도시 삭제, 새로운 도시를 배열에 넣어주는 방식으로 교체

구현 자체보다 LRU 알고리즘이 무엇인지 알아야 풀 수 있는 문제였다

나중에 다시 풀어볼 것!!!