[프로그래머스] 캐시

프로그래머스의 캐시 문제 풀면서 캐시에 대한 개념이 부족하여 문제자체를 이해하는데 시간이 걸렸다.

문제를 풀기 위해 필요한 기본 개념을 정리해 보았다.

• 캐시 히트(Cache Hit)란? : 참조하려는 메모리가 캐시에 존재하고 있을 때 (실행시간 1)
• 캐시 미스(Cache Miss)란? : 참조하려는 메모리가 캐시에 존재하지 않을 때 (실행시간 5)
• 캐시 크기(Cache Size)란? : 데이터를 저장하는 메모리 공간
• LRU(Least Recently Used)란? :  가장 오랫동안 참조되지 않은 페이지를 교체하는 방식
  • 새로운 데이터가 들어온 경우
    • 캐시에 넣어준다.
    • 캐시가 가득차있다면, 가장 오래된 데이터를 제거하고 넣어준다.
  • 존재하는 데이터가 들어온 경우
    • 해당 데이터를 꺼낸 뒤 가장 최근 데이터 위치로 보내준다.

 

 

아래의 입출력 예시4를 통해 문제를 이해해보자!

 

- 캐시크기: 5 

- 도시이름: ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]

- 실행시간: 52

 

5칸에 도시명을 차례로 넣을 수 있으며

해당 도시명이 캐시에 없으면

 - 캐시가 꽉 찼으면 가장 오래된 도시명을 지우고 해당 도시명 추가

 - 캐시가 꽉 차지 않았으면 해당 도시명 추가

 - 소요시간 ==5

해당 도시명이 캐시에 있으면

 - 캐시의 해당 도시명을 마지막 위치로 이동

 - 소요시간 ==1

 

 

1.  남은 도시리스트:  ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]

현재 소요시간: 0

 

2. 남은 도시리스트:  ["SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]

현재 소요시간: 25

 * "Jeju", "Pangyo", "Seoul", "NewYork", "LA"를 차례대로 추가 

 

3. 남은 도시리스트:  ["Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]

현재 소요시간: 30

 * 가장 오래된 "Jeju" 삭제 후, "SanFrancisco" 추가

 

4. 남은 도시리스트:  ["Rome", "Paris", "Jeju", "NewYork", "Rome"]

현재 소요시간: 31

 * index 1에 있던 "Seoul'을 가장 최근 위치(index 4)로 이동, 빈 부분 앞으로 땡겨서 채움

 

5. 남은 도시리스트:  ["Jeju", "NewYork", "Rome"]

현재 소요시간: 41

 * 가장 오래된 "Pangyo", "New York" 삭제 후, "Rome", "Paris" 추가

 

6. 남은 도시리스트:  [ ]

현재 소요시간: 52

 * 가장 오래된 "LA", "SanFrancisco" 삭제 후, "Jeju", "NewYork" 추가

 * index 3에 있던 "Rome"을 가장 최근 위치(index 4)로 이동, 빈 부분 앞으로 땡겨서 채움

 

 

이를 코드로 구현하면 아래와 같다!!

function solution(cacheSize, cities) {
    var answer = 0;
    let cityList =[];
    if(cacheSize ===0){return cities.length * 5} // 캐시크기가 0인 경우를 예외로 처리
    cities.map((val)=>{
        val = val.toUpperCase();
        let checkIdx = cityList.indexOf(val)
        // cityList에 val값이 없다면 -1을 반환함
        if(checkIdx != -1){ //cityList에 해당 도시명이 존재하면
            cityList.splice(checkIdx,1) //해당 도시명을 제거
            cityList[cityList.length] = val //마지막 위치에 추가
            answer+=1 
        }
        else{
            if(cityList.length===cacheSize){ // 캐시가 꽉찼으면
                cityList.shift() //가장 오래된 값 제거
            }
            cityList.push(val)
            answer+=5
        }
    })
    return answer;
}
console.log(solution(0, ["LA", "LA"]))

cacheSize가 0일 때 만약 cities에 ["LA", "LA"]가 있는 경우 

결과값이 10이어야 하는데

예외처리를 해주지 않으면 6이 나온다! 주의