P17680. 캐시

문제

제출 코드

• 사용 알고리즘 : 자료구조, 페이징 알고리즘(LRU)

LRU 알고리즘을 구현하면 되는 간단한 문제이지만, LRU를 알지 못한다면 절대 못푸는 문제.

그게 뭔지 안알려주니까,,

이 김에 다시한번 페이지 교체 알고리즘을 짚고 넘어가자.

페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법

1. FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법
   • 중요한 페이지가 오래 있었다는 이유만으로 교체될 수 있다.
   • 가장 오래된 페이지는 앞으로도 자주 사용될 가능성이 있다는 점.
2. LFU : 가장 적은 횟수를 참조하는 페이지를 교체
   • 참조될 가능성이 많음에도 불구하고 횟수가 적다는 이유로 최근에 사용된 프로그램을 교체시킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생
3. LRU : 가장 오랫동안 참조되지 않은 페이지를 교체
   • 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야 해서, 큰 오버헤드가 발생

List를 사용하여, 캐싱되어 있는 값이라면 저장된 값을 지워주고 안되어 있으면 넘칠 경우 가장 앞자리 값을 지워줬다.

그 뒤에 새로 읽은 값을 무조건 새로 리스트에 넣어주면, 리스트는 참조된 순으로 정렬된 값을 유지할 수 있다.

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0) return cities.length*5; // 캐시 크기가 0인 경우 예외처리

        int answer = 0;
        List<String> list = new ArrayList<String>();

        for(String c : cities){
            String city = c.toLowerCase();
            if(list.contains(city)) {
                answer++;
                list.remove((Object) city);
                list.add(city);
            }else{
                answer += 5;
                if(list.size() < cacheSize) list.add(city);
                else{
                    list.remove(0);
                    list.add(city);
                }
            }
        }

        return answer;
    }
}