[프로그래머스 - 2018카카오] [1차] 캐시

리뷰

소요시간: 40분

30분정도에 끝낼 수 있었는데, 테스트케이스 2개가 틀려서 디버깅을 조금 진행함.

 

 

문제풀이

제한

• 캐시크기 C: 0 ~ 30
• 도시 수 N: 1 ~ 100,000  → O(N)

 

 

유형

Goal: 캐시 크기에 따른 실행시간 측정. 입력된 도시이름 배열을 순서대로 처리할 때의 총 실행시간

* hit = 1, mis = 5, 캐시: LRU

→ 도시들을 한 번씩 순회하며, 캐시 hit/miss에 따른 실행시간을 측정하면 되므로 그냥 구현문제

 

 

설계

1. Cache는 List로 사용
LRU이므로 Queue를 사용할까 했지만, hit된 도시를 최신으로 갱신하기 위해서 remove를 해야하므로 List를 사용

 

2. Cache Hit / Miss 에 따른 구현

 

 

구현

import java.io.*;
import java.util.*;

class Solution {
    private static final int MISS = -1;
    public int solution(int cacheSize, String[] cities) {
        // edge case: cacheSize == 0
        int time = 0;
        if(cacheSize == 0) {
            for(int idx=0; idx<cities.length; idx++) {
                time += 5;
            }
            return time;
        }
        return pro(cacheSize, cities);
    }
    
    private int pro(int cacheSize, String[] cities) {
        //1. 도시이름 소문자로 통일: O(N)
        toLowerCase(cities);
        //2. 총 실행시간 계산
        int time = getTotalTime(cacheSize, cities);
        return time;
    }
    
    private int getTotalTime(int cacheSize, String[] cities) {
        List<String> cache = new LinkedList<>();
        int time = 0;
        
        for(int idx=0; idx<cities.length; idx++) {
            String city = cities[idx];
            // 캐시가 비어있는 경우 -> 캐시에 추가하고 시간갱신
            if(cache.isEmpty()) {
                cache.add(city);
                time += 5;
                continue;
            }
            // 캐시가 있는 경우 -> hit, miss 확인
            // 캐시 hit 확인
            int cachedIdx = checkCacheHit(cache, city);
            if(cachedIdx != MISS) { //캐시 hit이면 캐시를 갱신한다.
                cache.remove(cachedIdx);
                cache.add(city);
                time += 1;
            } else {    //캐시 miss면 캐시를 갱신한다.
                if(cache.size() == cacheSize) {
                    cache.remove(0);
                }
                cache.add(city);
                time += 5;
            }
        }
        return time;
    }
    
    
    // 캐시에 존재하는지 확인
    // return: 캐시가 있으면 해당 idx, 없으면 -1
    private int checkCacheHit(List<String> cache, String city) {
        for(int idx=0; idx<cache.size(); idx++) {
            if(cache.get(idx).equals(city)) {
                return idx;
            }
        }
        return -1;
    }
    
    private void toLowerCase(String[] cities) {
        for(int idx=0; idx<cities.length; idx++) {
            cities[idx] = cities[idx].toLowerCase();
        }
    }
}