[프로그래머스] 캐시 (2018 KAKAO BLIND RECRUITMENT)

programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시

2021-01-05

---

import java.util.ArrayList;
 
public class Solution17680 {
    public static int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0) return 5*(cities.length);
 
        int answer = 0;
            
        ArrayList<String> list = new ArrayList<>();
        for(int i = 0; i < cities.length; i++) cities[i] = cities[i].toLowerCase();
        
        for(int i = 0; i < cities.length; i++) {
            if(list.contains(cities[i])) {
                answer++;
                list.remove(cities[i]);
                list.add(cities[i]);
            }  else if(list.size() < cacheSize) {
                list.add(cities[i]);
                answer+=5;
            } else if(list.size() == cacheSize) {
                list.remove(0);
                list.add(cities[i]);
                answer+=5;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        String c[] = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
        System.out.println(solution(3, c));
    }
}

#문제풀이

문제에 따로 설명이 없어서, LRU 알고리즘, cache hit, cache miss에 대해서 간단하게 적어본다.
- LRU 알고리즘 (Least Recently Used)은 캐시에서 메모리를 다루는 알고리즘이다. 캐시는 문제에서 cacheSize처럼 제한된 양이 있다. 그래서 최근에 사용된적 없는 캐시의 메모리부터 삭제하여 데이트를 갱신시켜준다.
- cache hit은 참조하고자 하는 메모리가 이미 캐시에 존재함을 의미한다.
- cache miss는 참조하고자 하는 메모리가 캐시에 존재하지 않음을 의미한다.


1. cities 배열에 있는 값들을 다 lowercase로 통일시켰고, Arraylist를 이용하여 문제를 풀었다.

2. cities 배열을 돌면서, 3가지 케이스로 나눠서 생각했다.

3. 첫번째, 이미 list 안에 값이 들어가 있는 경우, cache hit이므로 실행시간은 +1을 해준다.

+) 여기서 이미 list 안에 있는 경우 list의 맨 뒤로 보내야하는데, 그 작업을 안해서 몇 개 테스트 케이스를 틀렸었다. 

 

4. 두번째는 list size가 cacheSize보다 없는 경우이다. 현재 list상에 존재하지도 않고 아직 cacheSize를 넘지 않았으니, 그냥 list에 추가해주면 된다. cache miss 이므로 실행시간에 +5를 해주면 된다.

5. 마지막으로는 이미 cacheSize만큼 list가 다 차버린 경우이다. 이런 경우에는 list의 첫번째값(제일 사용하지 않은)을 삭제하고, 새롭게 데이터를 추가해주면 된다. 마찬가지로 cache miss이므로 실행시간에 +5를 해주면 된다.