(프로그래머 – Kakao 2018) (1위) 현금

검토

소요 시간: 40분

30분 정도면 끝낼 수 있었는데, 두 개의 테스트 케이스가 틀려서 약간의 디버깅을 했습니다.

문제 해결

한계

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

범주

목표: 캐시 크기에 따른 실행 시간 측정. 입력된 도시명 배열을 순서대로 처리할 때 총 수행시간

* 적중 = 1, 미스 = 5, 캐시: LRU

→ 일단 도시를 순회하고 캐시 hit/miss에 따른 실행 시간을 측정하는 것으로 충분하기 때문에 구현상의 문제일 뿐입니다.

설계

1. 캐시를 리스트로 사용
LRU라서 Queue를 쓸까 생각했는데 히트시티를 최신으로 업데이트하려면 제거해야 하니까 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();
        }
    }
}