[알고리즘] 프로그래머스 캐시 :: 우유

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java 

프로그래머스

LRU에 대한 개념이 기억이 안나서 찾아보면서 풀어봤던 문제이다.
해야할 작업이 캐시에 있는 상태인지, 없는 상태인지 나눠서 처리해줘야하고
캐시크기가 0인 경우 예외 처리를 해주면 어렵지 않게 풀 수 있는 문제다

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

        /*
        LRU => 가장 오래 참조되지 않은 페이지 교체
        (시간을 기록해야한다는 단점이 있어서 오버헤드)

        cache hit : 해야할 작업이 캐시에 있는 상태
        cache miss : 해야할 작업이 캐시에 없는 상태
        */

        LinkedList<String> list = new LinkedList<>();

        if (cacheSize == 0) 
            return cities.length * 5;
        
        for (int i = 0; i < cities.length; i++) {

            String target = cities[i].toLowerCase();
            // 해야할 작업이 캐시에 있는지 없는지 확인
            boolean flag = false;
            int idx = 0;

            for (int j = 0; j < list.size(); j++) {
                // 있으면
                if (list.get(j).equals(target)) {
                    flag = true;
                    idx = j;
                }
            }

            // cache hit
            if (flag) {
                list.add(list.remove(idx));
                answer++;
            }
            // cache miss
            else {
                if (list.size() >= cacheSize) 
                    list.removeFirst();
                
                list.add(target);
                answer += 5;
            }
        }

        return answer;
    }
}