[프로그래머스] 캐시 (JAVA/자바) - 2018 카카오 기출

흶·2021년 9월 8일

알고리즘 프로그래머스

Algorithm

목록 보기

52/60

문제

프로그래머스>코딩테스트 연습>2018 KAKAO BLIND RECRUITMENT>[1차] 캐시 - https://programmers.co.kr/learn/courses/30/lessons/17680

풀이

LRU 방식으로 캐시 크기에 따른 실행시간을 측정하는 문제이다.

LRU 방식 : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법
cache hit : 실행시간 +1
cache miss : 실행시간 +5

city이름의 대소문자는 구분하지 않는다 라는 조건이 있으므로, 모든 문자를 소문자로 변경한다.
우선 캐시에 해당 city 문자열이 들어있는지 확인한다.
2-1. 캐시에 존재하면(cache hit), 실행 시간을 +1 한다. 이후 해당 index의 access time만 업데이트 해준다.
2-2. 캐시에 존재하지 않으면(cache miss), 실행 시간을 +5 한다.
- 캐시에 빈 공간이 있으면 그냥 데이터를 넣는다. (+access time도 기록한다)
- 캐시에 빈 공간이 없으면 access time이 가장 오래된 위치의 index를 찾아 해당 데이터를 변경한다. (+access time도 변경한다.)
단, 캐시의 크기가 0이라면 캐시에 아무 데이터도 저장해둘 수 없으므로 무조건 cache miss가 일어나기 때문에 예외처리 해주면 된다.

코드

class Solution {
    public static int solution(int cacheSize, String[] cities) {

        // 대소문자 구분이 없으므로 모두 소문자로 변경
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase();
        }
        
        String[] cache = new String[cacheSize]; 	// 캐시
        int[] cache_access_time = new int[cacheSize]; 	// 캐시에 들어있는 값이 참조된 time

        // initialize
        for (int i = 0; i < cacheSize; i++) {
            cache[i] = "";
        }

        int time = 0;
        
        if(cacheSize==0){  // 캐시 용량이 0이면 예외처리
            return 5 * cities.length;
        }

        int cnt = 0; // 캐시 안에 들어있는 데이터의 수
        
        for (int i = 0; i < cities.length; i++) {
            String now = cities[i];
            boolean cached = false;
            
            // 캐시에 now가 존재하는지 확인
            for (int j = 0; j < cacheSize; j++) {
                if (cache[j].equals(now)) { // cache hit
                    time ++; 
                    cache_access_time[j] = time;
                    cached = true;
                    break;
                }
            }
            
            if(!cached){ // cache miss
                time += 5; 
                
                if(cnt < cacheSize){ // 캐시 안에 남은 공간이 있으면 넣는다.
                    cache[cnt] = now;
                    cache_access_time[cnt++] = time;
                    
                }else{ // 남은 공간이 없다면 가장 오랫동안 참조되지 않은 위치(=참조 시간이 가장 작은 위치)를 찾아 변경한다
                    int min_idx = 0;
                    int min = time;
                    
                    for (int j = 0; j < cacheSize; j++) {
                        if(min > cache_access_time[j]){
                            min = cache_access_time[j];
                            min_idx = j;
                        }
                    }
                    
                    cache[min_idx] = now;
                    cache_access_time[min_idx] = time;
                }
            }
        }

        return time;
    }
}