[프로그래머스 알고리즘] 1차 캐시 (level 2)

문제

LRU

운영체제에서 배운 페이징 알고리즘이 나왔다.
LRU(Least Recently Used) 알고리즘은 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다. 캐시의 메모리는 한정되어 있고, 한번 참조된 데이터는 캐시에 적재 되는데, 캐시가 꽉 찬 상태에서 cache miss가 되면(캐시에 찾는 데이터가 없으면), 현재 캐시에 적재된 데이터 중, 어떤 데이터를 제거하고 새 데이터를 적재할 것인지 결정할 알고리즘이 필요하다. LRU는 그 알고리즘 중 하나이다.
++ 페이지 교체 알고리즘 -> https://velog.io/@kksshh0612/Virtual-Memory3

문제 풀이 (java)

LinkedList를 이용하였다.
1. 대소문자는 무시하기 때문에, 리스트에 문자가 있는지 확인할 때, .toLowerCase()를 사용하여 소문자로 통일시켜 주었다.
2. cache miss가 난 경우, 아직 캐시가 차지 않았으면 맨 뒤에 add / 캐시가 꽉 찼으면 리스트 맨 앞에서 빼고 (pollFirst()) 맨 뒤에 add
3. cache hit이 된 경우, 리스트에서 해당 데이터 빼고, 맨 뒤에 add
---> 여기까지 했는데, 제출 후 테스트에서 몇개 케이스에서 실패가 나왔다.
+조건. cache size가 0인 경우 처리를 해줘야 한다.

코드

import java.util.*;
//
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList list = new LinkedList<>();
//        
        if(cacheSize > 0){
            for(String city : cities){
//               
                if(!list.contains(city.toLowerCase())){       //miss
//                    
                    if(list.size() < cacheSize){        //아직 캐시가 차지 않았으면 add
                        list.add(city.toLowerCase());
                    }
                    else{
                        list.pollFirst();                    
                        list.add(city.toLowerCase());
                    }
                    answer += 5;
                }
                else{                       //hit
                    answer++;
                    list.remove(city.toLowerCase());
                    list.add(city.toLowerCase());
                }
            }
        }
        else{
            answer = 5 * cities.length;
        }
//       
        return answer;
    }
}