유형: 페이지 알고리즘 구현
문제: 프로그래머스 - [1차] 캐시

문제

---

풀이

LRU 알고리즘을 알고있다면 크게 어렵지 않게 구현할 수 있다. 일단 난 해당 안 됨

LRU (Least Recently Used) 알고리즘
가장 오래 참조되지 않은 페이지를 교체하는 방법

그래서 LRU 알고리즘에 대해 먼저 공부했다. 알고리즘을 이해하고 나니 재밌어서 따로 포스팅했다.
🔗 eunsilson - [Algorithm] LRU 페이지 교체 알고리즘의 실행 과정

---

문제에서 주어지는 cities 들을 cacheSize 크기의 리스트에 하나씩 넣으며 페이지 교체를 구현하면 된다.

LRU 알고리즘을 사용할 때 필요한 기능을 생각해봤다.

• 첫번째 값 삭제 → 가장 오래 참조되지 않은 페이지
• 캐시에 존재하는 값 추출
• 마지막 자리에 새로운 값 추가

ArrayList로 생각했던 기능들을 모두 구현할 수 있을 것 같아 ArrayList를 사용했다.

로직

1. cacheSize가 0일 때 cities * 5
   • 들어갈 수 있는 city가 없어 모두 miss
2. 소문자 변환
   • 문제에서 대소문자를 구분하지 않는다고 했으나, 입력 값에 같은 문자열인데 대소문자가 다른 값이 있어서 통일시킴
3. 리스트에 city가 있으면 hit + 해당 city를 다시 넣음
4. 리스트에 city가 없으면 miss
   • 캐시가 가득 찼다면 첫번째 city 삭제하고 city 넣기
5. 최종 time 반환

---

코드

import java.util.ArrayList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        
        if (cacheSize == 0) { // cache size 0
            return cities.length * 5;
        }

        // 소문자 변환
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase();
        }

        ArrayList<String> cache =  new ArrayList<>();
        int time = 0;

        for (String city : cities) {

            if (cache.contains(city)) { // hit
                time += 1;

                cache.remove(city);
                cache.add(city);

            } else { // miss
                time += 5;

                if (cache.size() == cacheSize) {
                    cache.remove(0);
                }
                cache.add(city);
            }
        }

        return time;
    }
}