[1차] 캐시

문제

풀이

import java.util.*;

class Solution {
    static int time=0;
    public int solution(int cacheSize, String[] cities) {
        Stack<String> stack = new Stack<>();
        String[] arr = new String[cities.length];
        
        //새로운 배열에 소문자 형태로 다 담아준다.
        int cnt=0;
        for(String str : cities){
            str = str.toLowerCase();
            arr[cnt++] = str;
        }

        //스택으로 LFU 구현
        for(String x : arr){
            //히트
            if(stack.contains(x)){
                stack.remove(stack.indexOf(x));
                stack.push(x);
                time+=1;
            }
            //미스
            else{
                stack.push(x);
                if (stack.size() > cacheSize) {
                    stack.remove(0);
                }
                time+=5;
            }
        }
        return time;
    }
}

LFU 란?
프로세스 처리 순서를 매기는 방식을 가장 오래 사용되지 않은 것을 제거시키면서 크기에 맞게 새로운 프로세스를 할당시켜주는 방식이다.

이 알고리즘을 나는 스택으로 구현했다. 왠만해서는 스택으로 구현해도 다 맞는다.

hit는 해당 프로세스가 들어올때 이미 캐시메모리에 그 프로세스가 할당되어있는 경우, 그 프로세스를 바로 삭제시키고 새 프로세스가 들어온다. 시간이 적게 걸림.
miss는 캐시메모리에 해당 프로세스 처리 하는 정보가 없다는 것. 그렇기 때문에 시간이 오래걸린다.
이러한 조건에 맞게 문제를 구현해서 풀면 간단하게 풀 수 있다.

여기서 대소문자를 구분하지 않는데, 전부 소문자로 바꿔서 새로운 배열에 정보들을 담아서 비교해주면 된다.