[프로그래머스] [1차] 캐시

문제

프로그래머스 2018 KAKAO BLIND RECRUITMENT [1차] 캐시

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

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

언어

자바스크립트(JavaScript)

 

참고

이 문제는 LRU에 대한 설명을 하지 않으므로 찾아봐야 한다. 간단하게 설명하자면 다음과 같다.

1. 캐시에 같은 데이터가 존재하면 그 캐시의 데이터를 읽는다. 이때 최근에 읽었다는 표시를 남겨야 한다.
2. 캐시에 같은 데이터가 존재하지 않으면 새로운 데이터를 넣는다. 만약 자리가 있으면 그냥 넣고 없으면 가장 읽은 지 오래된 데이터를 삭제한다.

자세한 내용은 여기를 참고했다. 공부를 위해 코드는 참고하지 않았고 개념만 참고하였다.

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)

 

접근 방법

1. 모두 소문자 처리한다.
2. 반복문으로 i 번째 도시 이름을 얻는다. 이 세 가지 경우의 수가 존재한다.
   
   1. 캐시에 i 번째 도시 이름과 같은 객체가 없으면 name이 도시 이름이고 idx가 i인 객체를 cacheArr에 삽입한다.
   2. 캐시에 i 번째 도시 이름과 같은 객체가 없는데 캐시가 차있으면 cacheArr의 맨 앞 객체를 삭제하고 새로운 객체를 cacheArr에 삽입한다.
   3. 캐시에 i 번째 도시 이름과 같은 객체가 있으면 idx를 i로 업데이트한다.
3. cacheArr을 객체의 idx 오름차순으로 정렬한다. idx가 작을수록 앞에 배치해서 캐시를 삭제할 때 앞의 요소를 삭제해서 오래된 객체를 삭제하도록 한다.

코드

function solution(cacheSize, cities) {
    let cacheArr = [];
    let time = 0;
    for (let i=0; i<cities.length; i++){
        // 모두 소문자 처리
        cities[i] = cities[i].toLowerCase();
        // 현재 도시 이름과 같은 데이터가 있으면 idx 업데이트
        // 현재 도시 이름과 같은 데이터가 없으면 새로 추가
        // 꽉 차있으면 젤 앞에 데이터 삭제 (idx가 클수록 최근이도록 정렬함)
        let findObj = cacheArr.find(ele=>ele.name===cities[i]);
        if (findObj === undefined){
            let obj = {name:cities[i], idx:i};
            cacheArr.push(obj);
            time += 5;
            if (cacheArr.length >cacheSize){
                cacheArr.shift();
            }
        }else{
            let findIdx = cacheArr.indexOf(findObj);
            cacheArr[findIdx].idx = i;
            time += 1;
        }
        // cacheArr를 idx에 따라 정렬 (idx가 클수록 최근이므로 이렇게 정렬)
        cacheArr.sort((a,b)=>{
            if (a.idx>b.idx){
                return 1;
            }else if (a.idx<b.idx){
                return -1;
            }
        })
        //console.log(cacheArr);
    }
    return time;
}

복기

1. LRU 알고리즘을 파악할 때 헷갈려서 파악을 제대로 하지 않고 코드를 작성해 시간을 많이 썼다.
2. 처음에 캐시에 자리가 있다고 무조건 데이터를 삽입하도록 작성해서 답을 틀렸다. 자리가 있더라고 같은 데이터면 idx만 업데이트하고 삽입하지 않아야 한다.