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

[문제 바로가기]👇

프로그래머스

 

💡풀이💡

이 문제는 LRU가 무엇인지 알고 있어야 풀 수 있었던 문제로 

캐시 교체 알고리즘인 LRU(Least Recently Used)를 구현하는 문제이다

LRU는 메모리에 남아 있는 캐시 중 가장 오래동안 사용하지 않은 캐시를 삭제하고 새로운 캐시로 교체하는 알고리즘이다

 

그렇기 때문에 계속해서 새로운 데이터가 캐시에 들어온다고 가정하면, 기본 동작은 FIFO이 된다

그래서 Queue로 접근을 했고 이미 캐시에 있는 데이터가 들어올 때는 해당 데이터를 삭제하고 다시 삽입하는 방식으로 구현했다

 

다만 한 가지 주의할 점은 문제에서는 캐시 크기가 0일 때도 있기 때문에 이 부분도 고려해서 처리를 해줘야 한다

 

전체 코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int time = 0; // 총 실행시간 저장
        
        ArrayDeque<String> cache = new ArrayDeque<>();
        for(int i=0; i<cities.length; i++) {
            String city = cities[i].toLowerCase(); // 전부 소문자로 통일
            if(cache.contains(city)) { // cache hit
                cache.remove(city);
                cache.offer(city);
                time += 1;
            }
            else { // cache miss
                if(cache.size() >= cacheSize) {
                    cache.poll(); // cache가 비어있으면 null을 리턴 
                }
                if(cacheSize > 0) cache.offer(city); // 캐시 크기가 0보다 클 때만 삽입
                time += 5;
            }
        }
        return time;
    }
}

 

 

---

참고자료

캐시 교체 알고리즘 LRU, LFU

[알고리즘] 캐시 교체 알고리즘 - LRU, LFU

 

LRU 캐시 자바

<알고리즘> 3. LRU 캐시 JAVA