[1차]캐시 2018 KAKAO BLIND RECRUITMENT(Lv.2)[프로그래머스]

---

 

<LRU(Least Recently Used) 알고리즘 이란?>

가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것.

 

LRU 알고리즘을 구현할때 Queue를 사용하면 편하다고 한다.

Java에서는 LinkedList가 Queue의 구현체 이다.

 

<LFU(Least Frequently Used)알고리즘 이란?>

가장 적게 참조한 페이지를 캐시에서 교체하는 것이다.

---

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int time = 0;
        int hit = 1;
        int miss = 5;
        LinkedList<String> q = new LinkedList<>();
        //캐시 크기가 0일경우 모두 miss, cities의 길이 * 5
        if (cacheSize == 0) {
            time = cities.length * 5;
            return time;
        }

        //캐시 크기가 0초과 일경우에만 캐시에 할당하여 작업 시작
            for (int i = 0; i < cities.length; i++) {
                //소문자 대문자 구분이 없으므로 대문자로 통일
                String upperCase = cities[i].toUpperCase();
                //캐시에 동일한 작업이 할당되어 있지 않은 경우 miss(time+=5), 작업을 추가함
                if (!q.contains(upperCase)){
                    q.addFirst(upperCase);
                    time+=miss;
                    //캐시에 동일한 작업이 존재하는 경우 hit(time+=1), 맨 앞으로 가져옴
                }else{
                    q.remove(upperCase);
                    q.addFirst(upperCase);
                    time+=hit;
                }
                //캐시 크기 보다 q의 크기가 클경우 제일 오래된 작업 삭제
                if (q.size()>cacheSize){
                    q.removeLast();
                }
            }
            return time;
    }
}