캐시

 

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

프로그래머스

 

Level 2

 

캐시 부적중에 관련된 간단한 구현문제.

 

주어진 캐시 크기를 토대로 데이터들을 받을때 적중/부적중 시 시간을 계산해 반환하면 된다.

 

최초에는 큐를 사용하려 했으나 중간 원소 제거 시 큐로는 LRU(가장 오래된 데이터 먼저 삭제) 을 구현하기엔 비효율적이라 리스트를 사용했다. 

 

1. 문자열을 차례로 받으며 대소문자 통합 처리를 먼저 진행한다. (필자의 경우 전부 소문자로 바꿨다) 재활용

2. 캐시 적중 시 적중한 데이터를 리스트에서 제거한다.

3. 캐시 부적중 시 캐시 크기가 최대치일 경우 0번 째 데이터를 리스트에서 제거한다. 

4. 각각 적중/부적중 시 시간 비용을 증가시켜준다. 

5. 리스트 맨 마지막에 현재 원소를 추가한다. 

6. 결과적으로 사용빈도에 따른 데이터 갱신과 더불에 메모리 최대치 또한 확인이 가능하다.

 

import java.util.*;

public class Solution { //캐시
    public int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0) return cities.length * 5; //캐시 사이즈 1일 경우 전체 캐시 부적중 처리
        int answer = 0;
        ArrayList<String> cache = new ArrayList<String>();
        for(String city : cities){
            StringBuilder cityFixBuilder = new StringBuilder();
            for(int idx = 0; idx < city.length(); idx++){
                char character = city.charAt(idx);
                character = Character.isUpperCase(character) ? (char) (character + ('a' - 'A')) : character;
                cityFixBuilder.append(character);
            }
            city = String.valueOf(cityFixBuilder); //문자열 대문자 -> 소문자 처리
            if(cache.contains(city)){ //캐시 적중 시
                cache.remove(city); //적중 원소 사용된 기간 초기화
                answer += 1;
            }else{ //캐시 부적중 시
                if(cache.size() == cacheSize) //캐시가 Full 일 경우
                    cache.remove(0); //사용 기간이 가장 오래된 원소 삭제
                answer += 5;
            }
            cache.add(city); //적중 시 : 리스트의 맨 뒤로 보내서 최근 사용된 것으로 처리 | 부적중 시 : 신규 추가
        }
        return answer;
    }
}