[프로그래머스] JavaScript - 캐시

📄 문제

- 캐시 알고리즘 LRU(Least Recently Used)를 사용해 캐시크기, 도시이름 배열이 주어지면 실행시간을 return

 

- 조건 

• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

- 주의점

• 도시이름이 대소문자가 섞여있고, 스펠링만 맞으면 같은 도시다.

문제가 너무 길어서 조건과 입출력 예제

---

📝 나의 풀이

function solution(cacheSize, cities) {
  let answer = 0;
  let box = [];
  let newArr = cities.map((item) => item.toLowerCase());
  newArr.forEach((city) => {
    if (!box.includes(city)) {
      box.push(city);
      answer += 5;
      if (box.length > cacheSize) {
        box.shift();
      }
    } else {
      answer++;
      let target = box.indexOf(city);
      box.splice(target, 1);
      box.push(city);
    }
  });
  return answer;
}

---

⌨ 접근법

1. 캐시사이즈 = 배열안의 요소 개수 이므로 사이즈를 체크할 box 배열 생성

2. 배열안의 요소 체크를 위해 요소들을 모두 소문자로 바꿔서 새로운 배열을 만든다. (newArr)

3. 새로운 배열로 반복문을 돌린다.

3-1. 만약 box 안에 검색하려는 요소가 없으면 그 요소를 push, answer를 5 올려준다.

3-2. 만약 박스의 길이 (캐시사이즈) 이상이면 가장 맨 앞의 요소를 없앤다.

3-3. 만약 box 안에 검색하려는 요소가 있으면 그 요소를 찾아서 없애고, 맨 뒤에 그 요소를 push,
       answer++ 해준다.

4. 3의 반복문이 모두 끝난 후 만들어진 answer를 return 한다.

---

📖 배운 점 

1. LRU 알고리즘

• Cache 알고리즘 중에 하나인 알고리즘!
• 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.
• 그린이 문제를 풀고 적어놓은 힌트 덕분에 이 문제를 수월하게 풀 수 있었던 것 같다.

---

😂 아쉬운 점

- 이번 문제를 풀면서 느낀게 문제도 문제지만 알고리즘 자체에 대한 공부를 개념부터 하면 좋을 것 같다.

- 개념을 익히고, 직접 만들어보고 어떨 때 사용하고 이런 것들을 정리하다 보면 내 코드의 수준이 높아질 것 같다.

- 책 사러 가야겠다!

---

📚 문제 링크

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

코딩테스트 연습 - [1차] 캐시