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

import java.util.LinkedHashMap;
import java.util.Map;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return cities.length * 5; // 캐시 크기가 0이면 모든 요청이 miss
        }

        int answer = 0;

        // LRU 캐시를 위한 LinkedHashMap 설정
        Map<String, Boolean> cachedMap = new LinkedHashMap<String, Boolean>(cacheSize, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Boolean> eldest) {
                return size() > cacheSize; // 크기를 초과하면 가장 오래된 항목 제거
            }
        };

        for (String city : cities) {
            String cityLowerCase = city.toLowerCase(); // 대소문자 구분 없도록 소문자로 변환

            if (cachedMap.containsKey(cityLowerCase)) {
                answer += 1; // cache hit
            } else {
                answer += 5; // cache miss
            }

            // 캐시에 값 추가 (LRU 순서 업데이트)
            cachedMap.put(cityLowerCase, true);
        }

        return answer;
    }
}

 

조건

1. 정수인 cacheSize의 범위가 0~30이다: 이는 곧 0에 대한 처리가 필요하다.

2. 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다: 대소문자에 대한 처리가 필요하다.

3. 총 실행시간"을 출력한다: cache hit + cache miss

4. 캐시 교체 알고리즘은 LRU를 사용한다.

5. cache hit일 경우 실행시간은 1이다.

6. cache miss일 경우는 실행시간은 5이다.

 

풀이

우선 LRU에 대한 이해가 필요했습니다. LRU란 LRU(Least Recently Used)로 이름에서도 알 수 있듯이 가장 최근에 사용된 것 기준으로 정렬되어야하고 메모리 초과시에 오래된 것을 순서로 삭제해주어 새로운 데이터를 입력해줍니다.

 

LRU를 구현하기 위해서는 우선 가장 최근의 것이 쌓이도록 데이터가 저장되어야 하고 삭제시에도 특정 위치를 정확히 삭제해주면서도 list를 정리해줄 필요가 없는 링크드리스트가 적합했습니다. 그런데 Java에서는 해당 기능이 적용된 LinkedHashMap이라는 좋은 자료형이 있어서 해당 것을 사용했습니다. 심지어 메모리가 초과될 경우에 직접 삭제할 필요없이 자동으로 오래된 것을 삭제까지 해줄 수 있는 기능도 있습니다.

 

cache hit, miss는 활용할 캐시메모리에 저장되어 있다면 cache hit, 캐시에 없는 데이터를 찾기 위해 직접 메인 메모리나 하드디스크에 접근해야될 경우나 데이터가 없을 경우에 cache miss입니다.

 

대소문자의 처리는 LowerCase로 처리해주었습니다. string에 담아 놓은 것은 매번 LowerCase을 사용할 경우 추가적으로 string을 담기 위한 메모리를 계속 소모하기 때문입니다.

 

cacheSize, 0.75f, true에 대한 부분은 cacheSize를 지정, 0.75f는 해시 충돌을 줄이기 위해 해시맵이 얼마나 가득 차면 용량을 늘릴지를 결정하는 값입니다. 이또한 해시맵에 대한 이해가 필요합니다. true 부분은 정렬 기준을 정해주는데 false일 경우 입력 순서를 기준으로 정렬되고 true의 경우 LRU규칙에 걸맞게 접근 순서를 기준으로 정렬해줍니다. 가장 최근에 접근한 항목이 맵의 끝으로 이동합니다.

 

느낀점

평소에 많이 공부해두었던 자료구조를 통해서 문제에 대한 이해가 쉬웠던 것 같습니다. 자료구조에 대한 학습과 캐시에 대한 학습까지 동시에 할 수 있던 좋은 문제였던 것 같습니다. 그리고 뭔가 카카오 문제는 정말 글을 자세하게 읽어야되는게 그냥 지나칠 수 있는 숨은 조건들이 많이 숨어 있는 것 같습니다. 항상 문제를 주의 깊게 보고 조건들을 잘 찾아야겠다는 생각을 또 다시하게 됐습니다.

 

 

참고 사이트

https://f-lab.kr/insight/understanding-lru-cache-20240605

LRU 캐시 알고리즘의 이해와 구현

 

문제

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