[프로그래머스][JAVA]Lv. 2 - 캐시

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

for (int i = 0; i < cities.length; i++) {
    cities[i] = cities[i].toUpperCase();
}

도시의 이름은 대소문자를 구별하지 않는다.

때문에 모든 도시를 대문자로 만들어 사용하였다.

 

LRU 알고리즘

cache size가 3일 때,

처음 A B C가 들어온다고 하면 3차례의 cache miss가 일어난다.

다음 차례가 B라고 한다면 cache의 상태는 A C B가 되고 cache hit가 된다.

다음 차례가 D라고 한다면 cache의 상태는 C B D가 되고 cache miss가 된다.

빈 cache에 A가 들어오고 다음에 A가 들어오면 cache의 상태는 A일 것이다.

그리고 다시 B가 들어오고 A가 들어오면 상태는 B A가 될 것이다.

cache size가 0이라면 모든 입력은 cache miss가 될 것이다.

이를 고려하여 코드를 작성하였더니 다음과 같았다.

import java.util.ArrayList;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        ArrayList<String> al = new ArrayList<>();

        int cache_hit = 0;
        int cache_miss = 0;

        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toUpperCase();
        }
        if (cacheSize != 0) {
            for (int i = 0; i < cities.length; i++) {
                if (al.size() == cacheSize && !al.contains(cities[i])) {
                    al.remove(0);
                    al.add(cities[i]);
                    cache_miss++;
                } else if (al.size() < cacheSize && !al.contains(cities[i])) {
                    al.add(cities[i]);
                    cache_miss++;
                } else if (al.size() < cacheSize && al.contains(cities[i])) {
                    al.remove(cities[i]);
                    al.add(cities[i]);
                    cache_hit++;
                } else {
                    al.remove(cities[i]);
                    al.add(cities[i]);
                    cache_hit++;
                }
            }
        } else {
            for (int i = 0; i < cities.length; i++) {
                cache_miss++;
            }
        }
        
        return cache_hit + (cache_miss * 5);
    }
}

cache_hit와 cache_miss를 증가시키고 계산하여 결과로 출력하였다.