2023. 3. 13. 17:40ㆍAlgorithm
프로그래머스의 캐시 문제 풀면서 캐시에 대한 개념이 부족하여 문제자체를 이해하는데 시간이 걸렸다.
문제를 풀기 위해 필요한 기본 개념을 정리해 보았다.
- 캐시 히트(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이 나온다! 주의
'Algorithm' 카테고리의 다른 글
[프로그래머스] 소수 찾기 (0) | 2023.03.16 |
---|---|
[프로그래머스] 뉴스 클러스터링 (1) | 2023.03.15 |
[프로그래머스] 타겟 넘버 (0) | 2023.03.10 |
동적 계획법(Dynamic Programming) (1) | 2023.03.10 |
[프로그래머스] N으로 표현 (0) | 2023.03.09 |