[프로그래머스] 카카오_캐시 (자바 풀이)

문제

https://programmers.co.kr/learn/courses/30/lessons/17680?language=java 

코딩테스트 연습 - [1차] 캐시

풀이

이 문제는 LRU 알고리즘을 구현한다고 볼 수 있다. 혹시 LRU 알고리즘에 대해 모른다면 다음을 참고하자.

[운영체제] 페이지 교체 알고리즘 (FIFO/OPT/LRU/LFU/MFU)

LRU 알고리즘을 구현하기 위해 HashMap 자료구조를 사용했다. key는 City의 이름, value는 age(나이)를 나타낸다. 따라서 cache에 있는 모든 도시들은 1씩 나이를 먹고, 만약 hit 하면 age를 0으로 초기화해준다. miss일 경우 cache가 비어있다면 새로 넣어주면 되고, cache가 꽉차 있으면 가장 나이를 많이 먹은(==최근까지 사용되지 않은) 도시를 제거한다.

이때, cacheSize가 0이라면 어떤 도시도 넣을 수 없다는 Case를 고려해주어야한다!! (이것 때문에 Case7,17 실패함 ㅠㅠ)

코드

import java.util.*;
 
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        HashMap<String, Integer> cache = new HashMap<>();
        
        for(int i=0; i< cities.length; i++){
            String city = cities[i].toUpperCase();
            if(cache.containsKey(city)){   // hit
                answer +=1;
                cache.put(city, 0);
            }else{  // miss
                answer += 5;
                if(cacheSize == 0) continue;    // cache에 넣을 수 없음
                if(cache.size() >= cacheSize){   // cache 꽉참, 가장 오래 사용 안된 것 삭제
                    int max = 0;
                    String maxKey = "";
                    for(String key : cache.keySet()){
                        if(max < cache.get(key)){
                            max = cache.get(key);
                            maxKey = key;
                        }
                    }
                    cache.remove(maxKey);   
                }
                cache.put(city, 0);
            }
            /* aging */
            for(String key : cache.keySet()){
                cache.put(key, cache.get(key)+1);    
            }
        }
        
        return answer;
    }
    
}

결과