프로그래머스 / Level 2 , 2018 KAKAO BLIND RECRUITMENT , [1차] 캐시 자바스크립트 , JS

프로그래머스 / Level 2 , 2018 KAKAO BLIND RECRUITMENT , [1차] 캐시 자바스크립트 , JS

 

 

문제 출처

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

프로그래머스

 

 

 

풀이

그냥 무작정 집어 넣으면 안되고 문제에서 요구하는 LRU (Least Recently Used) 알고리즘을 적용해야한다.

 

1. 캐시 안에 넣을려는 값이 담겨져 있다면 cache hit 인 경우로 실행시간은 1초만 증가한다. 

중요한 점은 캐시에서 cache hit 인 값을 삭제하고 새로 맨 뒤로 추가해주는 것이다.

 

(그냥 무작정 맨앞에 있는 값을 삭제해버리면 안됨! 주의)

 

 

ex ) 

 

caheSize 가 5인 상황에서 캐시에 [1, 2, 3 ,4, 5] 가 담겨져 있다 가정하자

 

다음 값이 2가 들어올경우 cache hit 가 발생한다.

 

이 경우 캐시 값은 [1, 2, 3, 4, 5]  => [1, 3, 4, 5, 2] 가 되게 된다.

 

[2, 3, 4, 5, 2] 가 되는 게 아니니 주의하자.

 

 

 

2. 이외의 경우들은 cache miss 인 경우이므로 그냥 차례대로 넣어주고 실행시간은 5초 증가한다.

 

이 경우에는 caheSize 보다 커지는지 확인해주고 커진다면 가장 먼저 넣었던 값을 삭제해준다.

 

 

 

 

 

 

 

 

 

정답

 

function solution(cacheSize, cities) {
  var answer = 0;
  let arr = [];
  for (let i of cities) {
    let tmp = i.toLowerCase();
    if (arr.includes(tmp)) {
      arr = arr.filter((e) => e !== tmp);
      answer += 1;
      arr.push(tmp);
    } else {
      answer += 5;
      arr.push(tmp);
      if (arr.length > cacheSize) {
        arr = [...arr.splice(1, cacheSize)];
      }
    }
  }
  return answer;
}