[프로그래머스] [1차] 캐시

 

[프로그래머스] [1차] 캐시 (LV.2)

 

문제링크

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

프로그래머스

 

 

풀이 과정

 

1. 우선 캐시 사이즈가 0이면, cache hit이 존재하지 않으므로, 배열길이 * 5를 해서 바로 return 해준다.

 

2. 캐시 사이즈에 맞게 문자열을 담을 배열 cache과 해당 문자열이 캐시에 몇 턴동안 담고 있었는지 카운트할 정수 배열 cnt을 만들어주었다.

 

3. 먼저 입력받은 도시이름 배열 cities를 for문으로 돌며 하나씩 캐시에 넣어준다. 다만 넣어줄 때 LRU 캐시 교체 알고리즘을 따라서 크게 두 방법으로 나뉜다.

1. 캐시에 해당 도시이름이 있는지? (cache hit)
2. 캐시에 해당 도시이름이 없는지? (cache miss)

 

1번과 같다면 cache hit이므로 실행시간이 1이기 때문에 리턴값에 +1을 해주고, 카운트 배열은 0으로 초기화해준다. 이 때, 다른 배열들은 한 턴을 도는 것이므로 카운트 배열에 +1을 해준다. 참고로 도시 이름을 비교할 때는 equalsIgnoreCase()를 사용하여, 대소문자 구분 없이 비교하도록 해준다.

 

2번과 같다면 cache miss이다. 카운트 배열을 돌며 제일 큰 값(제일 캐시에 오래 머무른 값)을 찾아낸다. 해당 인덱스를 구하여, 캐시 배열에 도시 이름을 업데이트 해주고, 카운트는 0으로 초기화한다. 실행시간이 5이므로 리턴값에 +5를 해준다.

 

 

 

 

코드

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

        if(cacheSize == 0) {
            return cities.length * 5;
        }

        int[] cnt = new int[cacheSize];
        String[] cache = new String[cacheSize];

        for(int i = 0; i < cities.length; i++) {

            String city = cities[i];
            boolean b = true;
            int val = -99999999;
            int idx = 0;

            for(int j = 0; j < cache.length; j++) {
                if(city.equalsIgnoreCase(cache[j])) {
                    cnt[j] = 0;
                    b = false;
                    answer += 1;
                } else {
                    cnt[j] += 1;
                }
            }


            if(b) {
                for(int j = 0; j < cnt.length; j++) {
                    if(val < cnt[j]) {
                        val = cnt[j];
                        idx = j;
                    }
                    cnt[j] += 1;
                }
                cache[idx] = city;
                cnt[idx] = 0;
                answer += 5;
            }

        }

        return answer;
    }
}