159. 캐시 Javascript

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

프로그래머스

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - DB 캐시를 적용할 때 캐시 크기에 따른 실행시간을 구하라
• 주어진 자료는 무엇인가?
   - 캐시 크기(cacheSize)와 도시이름 배열(cities)
  
• 조건은 무엇인가?
   - cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 
   - cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개
   - 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다
   - 도시 이름은 최대 20자로 이루어져 있다.
   - 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력
   - 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용
   - cache hit일 경우 실행시간은 1
   - cache miss일 경우 실행시간은 5

2. 계획

1. cities를 순회하면서 cache배열 안에 있는지 체크 한다.
2. 캐시가 사용되면 가장 최근에 사용한 값이 되므로 맨 뒤에 넣는다. 
   2-1. 캐시가 있는 경우, cache배열에서 city값을 지워주고, 맨 뒤에 city값을 push해줍니다. 그리고 answer+=5
   2-2. 캐시가 없는 경우, cache배열에서 맨 앞의 값(사용한지 가장 오래된 값)을 제거하고 맨 뒤에 city값을 push해줍니다. 그리고 answer+=1

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const solution = (cacheSize, cities) => {
  // cities를 순회하면서 cache배열 안에 있는지 체크 한다.
  // 캐시가 사용되면 가장 최근에 사용한 값이 되므로 맨 뒤에 넣는다.
  // 2 - 1. 캐시가 있는 경우, cache배열에서 city값을 지워주고, 맨 뒤에 city값을 push해줍니다.그리고 answer += 5
  // 2 - 2. 캐시가 없는 경우, cache배열에서 맨 앞의 값(사용한지 가장 오래된 값)을 제거하고 맨 뒤에 city값을 push해줍니다.그리고 answer += 1

  let cache = [];
  let time = 0;
  if (cacheSize === 0) return cities.length * 5;

  const city = cities.map((it) => it.toLowerCase());

  city.map((it) => {
    if (cache.includes(it)) {
      cache.splice(cache.indexOf(it), 1);
      cache.push(it);
      time += 1;
    } else {
      if (cache.length === cacheSize) {
        cache.shift();
      }
      cache.push(it);
      time += 5;
    }
  })
  return time;
};

test('runTime', () => {
  expect(solution(3, ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"])).toEqual(50);
  expect(solution(3, ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"])).toEqual(21);
  expect(solution(2, ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"])).toEqual(60);
  expect(solution(5, ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"])).toEqual(52);
  expect(solution(2, ["Jeju", "Pangyo", "NewYork", "newyork"])).toEqual(16);
  expect(solution(0, ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"])).toEqual(25);
});