자바스크립트 릿코드 #번외 카카오 코딩테스트 2017 공채 문제 풀이 3

들어가며

이 포스팅에서는 leetcode 추천 문제 top 75를 자바스크립트로 풀어보며 자바스크립트 공부와 알고리즘 공부를 동시에 합니다. 문제와 풀이를 적을 건데, 틀린 부분이나 더욱 개선될 부분이 있다면 댓글로 달아주시면 정말 감사하겠습니다.

번외편

이번에는 번외적으로 leetcode 추천 문제 75선이 아닌 카카오 신입 공채 문제였던 문제를 풀이해보겠습니다.

문제

캐시

문제 설명

문제 개요

예제

풀이 과정

일단 코딩테스트 문제인만큼 빠르게 푸는데 초점을 두었습니다.

문제를 간단히 추려보면, LRU의 비용 계산을 하라는 것입니다.

LRU는 설명하자면 간단합니다.

1. 총 n개의 캐시가 있다.
2. n개의 캐시에는 각각 데이터가 1개씩 저장될 수 있다.
3. 데이터는 쓰여지지 않을수록 뒤로 밀려나며, 새로운 데이터가 들어오면 가장 뒤에 있던 데이터가 제거된다.

제가 작성한 해답 소스는 다음과 같습니다

function cacheTimeCalc(n, cities) {
  let cityMap = {};
  let timeCount = 0;
  let costSum = 0;
  let noCacheCost = 5;
  let cacheCost = 1;

  cities.map(city => {
    city = city.toLowerCase();

    if (cityMap[city] === undefined) {
      cityMap[city] = timeCount;
      timeCount++;
      costSum += noCacheCost;
    } else {
      if (cityMap[city] < timeCount - n) {
        costSum += noCacheCost;
      } else {
        costSum += cacheCost;
      }
      if (cityMap[city] !== timeCount) {
        cityMap[city] = timeCount;
        timeCount++;
      }
    }
  });

  return costSum;
}

console.log(
  cacheTimeCalc(3, [
    'Jeju',
    'Pangyo',
    'Seoul',
    'NewYork',
    'LA',
    'Jeju',
    'Pangyo',
    'Seoul',
    'NewYork',
    'LA'
  ])
);
console.log(
  cacheTimeCalc(3, [
    'Jeju',
    'Pangyo',
    'Seoul',
    'Jeju',
    'Pangyo',
    'Seoul',
    'Jeju',
    'Pangyo',
    'Seoul'
  ])
);
console.log(
  cacheTimeCalc(2, [
    'Jeju',
    'Pangyo',
    'Seoul',
    'NewYork',
    'LA',
    'SanFrancisco',
    'Seoul',
    'Rome',
    'Paris',
    'Jeju',
    'NewYork',
    'Rome'
  ])
);
console.log(
  cacheTimeCalc(5, [
    'Jeju',
    'Pangyo',
    'Seoul',
    'NewYork',
    'LA',
    'SanFrancisco',
    'Seoul',
    'Rome',
    'Paris',
    'Jeju',
    'NewYork',
    'Rome'
  ])
);
console.log(cacheTimeCalc(2, ['Jeju', 'Pangyo', 'NewYork', 'newyork']));
console.log(cacheTimeCalc(0, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']));

원래의 LRU는 링크드리스트로 구현되어 삽입 삭제 등의 연산을 하지만, 이 문제에서는 그냥 소요시간만 구하면 되므로 삭제를 할 필요가 없이 삽입만 하였습니다.

timeCount라는 변수가 위 소스 로직의 핵심을 담고 있습니다.

총평 및 배운점

LRU라는 어려운 용어 때문에 정답률이 낮았는지 이 문제는 정답률이 낮았다고 합니다. 용어에 당황하지 않는 습관을 들이는 것도 괜찮을 것 같습니다.