프로그래머스 js 캐시

이명진·2022년 5월 6일
0

코드카타

목록 보기
24/68

2018년도 카카오 블라인드 채용 문제이다.

문제 설명

데이터가 주어지고 이를 캐시 값에 저장을 한다.
캐시 저장소의 크기도 주어지는데 캐시에 있는 값을 불러오면 1초가 들고
새로 불러오면 5초가 소요 된다.

캐시 교체 알고리즘은 LRU 를 사용한다.

LRU

잘 몰랐는데 검색해서 공부를 조금 하고 간략하게 정리해둔다.
LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는것이다.
만약 크기가 3인 캐시가 있는데 캐시가 꽉차있을때 캐시 안에 있는 값을 불러오면
그게 캐시 배열 인덱스 맨 앞자리로 이동한다.

첫 풀이

function solution(cacheSize, cities) {
    let answer = 0;
  	let cache = [];
  
  cities.map((x,i)=>{
   
    if(cache.length===cacheSize){
    
    	let isCache = cache.findIndex(index=>{
        // console.log(index,x)
       return index.toUpperCase() === x.toUpperCase()
      })
      if(isCache!== -1){
        
        //hit
        cache.splice(isCache,1)
        cache.unshift(x)
        answer+=1
      }else{
        //miss
        cache.pop();
        cache.unshift(x)
        answer+=5
      }
      
    }else{
    	 cache.unshift(x);
      answer+=5;
    }
  })
	
    return answer;
}

이렇게 풀었는데 대략 2할 정도 틀렸다.
hit과 miss를 만약 모른다면 .
(hit과 miss 딱 해석만 해도 맞았다 놓쳤다 이다. 캐시에 값이 있을때 hit이고 없을때 miss이다. hit은 1초 miss는 새로 불러와야 하니 5초이다. )

질문하기의 힌트를 찾아보니 나는 캐시가 꽉차 있을 경우에만 캐시를 지우고 맨앞으로 불러오는 일을 하게 로직을 작성해 두었다.

꽉 차기 전에도 캐시에 값이 있다면 그 값을 맨앞으로 이동시키는 일을 해야 한다.

두번째 풀이

function solution(cacheSize, cities) {
    let answer = 0;
  	let cache = [];
  cities.map((x,i)=>{
   

    
    	let isCache = cache.findIndex(index=>{
        // console.log(index,x)
       return index.toUpperCase() === x.toUpperCase()
      })
      if(isCache!== -1){
        
        //hit
        cache.splice(isCache,1)
        cache.unshift(x)
        answer+=1
      }else{
        //miss
        if(cache.length===cacheSize){
           cache.pop();
        }
      
        cache.unshift(x)
        answer+=5
      }
      
  })
		console.log(cache)
    return answer;
}

다시 로직을 수정하였다. hit miss 상태를 우선으로 두고 로직을 풀어 나갔다.
근데 7번과 17번이 틀리는 것이었다.
왜 틀리는지 몰라서 다시 질문하기 힌트를 보게 되었는데
카카오 정식 해설에서 설명한것 처럼 이번 케이스에는 캐시크키가 0일 때의 조건도 있었다.
캐시 크기가 0일 경우 예외 처리를 해주면 된다.
캐시크기가 0일 경우 캐시를 쓸수 없으니 다 새로불러와야 한다.

맞춘 풀이

function solution(cacheSize, cities) {
    let answer = 0;
  	let cache = [];
  if(cacheSize==0){
		return cities.length*5
  }
  cities.map((x,i)=>{
   

    
    	let isCache = cache.findIndex(index=>{
        // console.log(index,x)
       return index.toUpperCase() === x.toUpperCase()
      })
      if(isCache!== -1){
        
        //hit
        cache.splice(isCache,1)
        cache.unshift(x)
        answer+=1
      }else{
        //miss
        if(cache.length===cacheSize){
           cache.pop();
        }
      
        cache.unshift(x)
        answer+=5
      }
      
  })
		console.log(cache)
    return answer;
}

힌트를 통해서 쉽게 문제를 푼것 같다. 이렇게 문제를 풀다가 막히면 힌트를 보게 되는데 실전에서는 어떻게 디버깅을 해나가야 할지..
예외 케이스를 어떻게 찾아야 할지 고민이다.

profile
프론트엔드 개발자 초보에서 고수까지!

0개의 댓글