[프로그래머스] 캐시

최종 풀이

function solution(cacheSize, cities) {
    let cachedList = new Array(cacheSize).fill('');
    let answer = 0;

    // 대소문자 구분 없이 모두 대문자로
    const capitalCities = [...cities].map((item) => item.toUpperCase());

    // 배열 순회
    for (const el of capitalCities) {

        // el이 캐시 배열에 이미 존재
        if(cachedList.includes(el)) {

            // el 제외한 리스트 생성
            const filteredList = cachedList.filter((i) => i !== el);

            cachedList = [el, ...filteredList];

            answer += 1;
        } else if (cacheSize === 0) {
        // cacheSize가 0일 때 예외처리
            answer += 5;
        } else {
        // el이 캐시 배열에 없을 때

            // tmp 초기화 및 cachedList 복사
            let tmp = [...cachedList];

            // 다른 배열들 한 칸씩 이동
            cachedList.forEach((item, idx) => {
                if (idx !== 0) { // 인덱스 0은 제외
                    tmp[idx] = cachedList[idx - 1];
                }
            })

            // 맨 앞에 해당 요소 추가
            tmp[0] = el;

            // tmp -> cachedList로 요소 옮기기
            cachedList = [...tmp];

            answer += 5;
        }
    }
    return answer;
}

💡 핵심 아이디어

LRU 페이지 교체 알고리즘
가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘

1. 배열을 순차적으로 캐시 배열에 할당
   캐시 크기만큼 빈 문자열("")로 초기화한 cachedList를 준비한 뒤, 방문하는 도시들(cities)을 대소문자 구분 없이 모두 대문자로 변환한 capitalCities 배열을 만든다.

2. Cache Hit
   • 해당 요소가 이미 캐시에 존재하면 실행시간 1을 더한다.
   • 요소를 캐시 맨 앞(index 0)으로 이동시키고, 기존 요소들은 뒤로 한 칸씩 미룬다.

3. Cache Miss
   • cacheSize가 0이라면 캐시를 사용할 수 없으므로 실행시간 5를 더하고, 캐시 상태는 그대로 둔다.

   • 그렇지 않으면 실행시간 5를 더한다.
     1. cachedList를 복사해 새로운 배열 tmp를 만든다.
     2. cachedList의 각 요소를 한 칸씩 뒤로 이동시켜 tmp에 반영
     3. tmp[0]에 새 요소를 추가
     4. 최종적으로 tmp를 cachedList에 덮어씌운다.

😵‍💫 부딪혔던 문제

배열 복사 이슈

} else {
  // el이 캐시 배열에 없을 때
  const tmp = cachedList; // 잘못된 복사

  // 다른 배열들 한 칸씩 이동
  cachedList.forEach((item, idx) => {
    if (idx !== 0) {
      console.log('cachedList', cachedList);
      tmp[idx] = cachedList[idx - 1];
    }
  });

  // 맨 앞에 해당 요소 추가
  tmp[0] = el;
  cachedList = tmp;

  answer += 5;
}

• 위 코드는 tmp = cachedList로 할당했기 때문에, tmp와 cachedList가 같은 메모리 주소를 참조하게 된다.
• 따라서 tmp[idx] = … 식으로 값을 변경하면, 원본인 cachedList도 함께 변경되어 의도치 않은 동기화가 발생한다.

배열 복사의 예시

let hobbies = ['Sports'];
let newHobbies = hobbies;   // 메모리 주소 복사
newHobbies.push('Cooking');

console.log(hobbies);      // ["Sports", "Cooking"]
console.log(newHobbies);   // ["Sports", "Cooking"]

해결법

Spread 연산자를 사용하여 배열을 깊은 복사한 뒤, 복사본을 수정해야 한다.

let tmp = [...cachedList];

배운 점 및 향후 개선점

• 문제 조건을 꼼꼼히 읽고 예외 케이스 확인하기
  - cacheSize === 0인 경우를 간과하면 테스트 케이스가 실패한다.
  - 도시 이름 대소문자 구분이 없다는 조건을 반드시 반영해야 한다.

• 배열 복사를 정확히 이해하기
  - JS에서 배열을 tmp = originalArray로 할당하면 메모리 주소만 복사된다.
  - 새로운 배열을 만들고 싶다면 반드시 tmp = [...originalArray]처럼 깊은 복사를 사용해야 한다.

• 향후 개선점
  캐시 상태를 배열이 아닌 자료구조(Set + Queue 조합, 또는 순서가 관리되는 Map)로 관리하면, 코드가 더 깔끔하고 효율적일 수 있다.