[Programmers/JAVA] [1차] 캐시

 

내 코드

import java.util.LinkedHashMap;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        //LinkedHashMap을 이용하여 순서있게 값을 저장하려고 함.
        LinkedHashMap<String, String> list = new LinkedHashMap<String, String>(){
            @Override//removeEldestEntry를 오버라이드해서 list의 size가 cacheSize보다 커지면 오래된 값을 삭제함.
            protected boolean removeEldestEntry(java.util.Map.Entry<String, String> eldest) {
                return size() == cacheSize+1 ? true : false; 
            }
        };

        //list에 값 넣기
        for(String city:cities) {
            city=city.toLowerCase();//대소문자 구별을 없애기 위해
            if(list.containsKey(city)) {//list에 city가 존재한다면
                list.remove(city);//지우고
                list.put(city, city);//추가
                answer+=1;
            }else {//list에 city가 존재하지않는다면
                list.put(city, city);
                answer+=5;
            }
        }
        
        return answer;
    }
}

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        //queue를 사용. 선입선출.
        Queue<String> list_q = new LinkedList<>();
        if(cacheSize==0) {//cachesize가 0일때
            answer=cities.length*5;
        }else {
            for(String city : cities) {
                city=city.toLowerCase();
                if(list_q.contains(city)) {//city값을 포함하고 있다면
                    list_q.remove(city);
                    list_q.add(city);
                    answer+=1;
                }else {
                    if(list_q.size()==cacheSize) {//queue size가 cachesize면
                        list_q.remove();//먼저 들어간 값 제거
                    }
                    list_q.add(city);
                    answer+=5;
                }
            }
        }
        
        return answer;
    }
}

 

느낀점

첫 번째 풀이는 linkedHashMap 사용, 두번째 풀이는 queue를 사용했다.

이 문제에 쓰인 LRU 캐시에 대해서 공부했다. 기본지식이 필요했던 문제였다. LRU 캐시란 값이 중복되면 기존에 갖고있던 값을 최신으로 가져오고, 중복되지않다면 추가. 메모리가 부족하면 가장 오래된 값을 삭제. 하는 식이다. 섭입선출(FIFO)이 생각나서 queue 를 사용했다. 그 후 사람들이 LinkedHashSet을 많이 사용하길래 어떤건가 찾아보던 중 LinkedHashMap에 대해서 알게되었고 LinkedHashMap의 removeEldestEntry를 오버라이드해서 사용하면 편리할 것 같아 사용해보았다.

확실히 LinkedHashMap이 더 편한것같다. list가 cacheSize를 오버했는지 안했는지, 오래된 값을 remove 해줘야하는지 말아야하는지 신경쓰지 않아도 돼서 더 편했고 cacheSize가 0일때를 고려하지않아도 알아서 해줘서 편했다!

 

queue 사용 결과

LinkedHashMap을 사용한 결과

LinkedHashMap이 전반적으로 빠른것 같은데 가끔 더 느릴때도 있고.. 어떤 차인지는 모르겠다.