[프로그래머스 2단계] 캐시

🔒 2단계 - 캐시

🤔 문제 이해

해당 문제는 CACHE와 LRU(Least Recently Used)에 관한 이해가 필요했다.

흔히 아는 CACHE.
내가 이미 방문한 홈페이지를 재방문한다면 처음 이 페이지를 방문했을때보다,
일찍 로드 된 것을 느껴본 적이 있을 것이다. 이것이 CACHE가 페이지가 저장되어 있기 때문.

LRU는 캐시에 대한 알고리즘으로, CACHE가 꽉 찼을때, 가장 오래된 CACHE를 제거하는 기법이다.

이 문제에서는 CACHE HIT 과 CACHE MISS만 파악하면 된다.

아래 그림에서 HIT이라 쓰여진 부분이 HIT, 글씨가 없는 부붙이 MISS 이다.

간단히, 이미 캐시에 저장되어 있는 자료라면, HIT을 발생시킨다.

예로, 그림 3번째 줄 <add 1 Hit> 부분을 보면, 이 전 CACHE [1,2]에 1이 포함되어 있으므로,
HIT가 발생하고, 가장 최신 CACHE로 추가된다.

그림 마지막 줄 <add 4>를 보면, 이 전 CACHE [1,3,2]에 4가 없으므로, MISS가 발생하고,
CACHE가 가득 차 있으므로, 가장 오래된 1을 제거했다.

📌 테스트케이스 추가 힌트

해당 문제는 추가 테스트 케이스가 필요하지 않았다.

✍️ 풀이법

먼저, String 타입을 담는 List 를 선언 해 주어, CACHE의 크기만큼 자료를 담았다.

담을때, 
HIT가 발생하면, 최신화(지우고 다시 추가)하고 실행시간에 +1,
MISS가 발생하면, 실행시간 +5.

List의 크기가 CACHE 사이즈를 넘어서면, LRU 기법에 의해 가장 오래 된 CACHE를 삭제했다. (List의 0번째 인덱스)

🗝️ 풀이

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        List<String> ar = new ArrayList<>();

        for(String i : cities){
            i = i.toUpperCase();

            if(ar.contains(i)){
                answer += 1;
                ar.remove(i);
            }else{
                answer += 5;
            }

            ar.add(i);

            if(ar.size() > cacheSize){
                ar.remove(0);
            }
        }
        return answer;
    }
}