Lv.2 캐시 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(36분6초)

아이디어

처음에 이 문제를 보고 엥 이게 Lv2라고 1아닌가 생각할 정도로 간단하게 구현해서 제출했는데 60점이 나왔다.
내가 놓친 부분이 있었다.

 

그건바로 문제에서 LRU방식으로 구현하라 했는데
난 miss가 났을때 큐가 가득차있다면 제일 앞에 있는 city를 빼고 있었던 것이었다.

LRU(Least Recently Used) 이름 그대로 최근에 최소로 사용된이라는 뜻인데 운영체제 배울때 배운 스케줄링 기법이었다.
만약 내가 이걸 모르는 상태로 풀었다면 문제 테스트케이스에도 나처럼 간단하게 풀어도 걸리지 않기에
그냥 넘어갔을 것이고 시험때는 점수도 모르니 틀린지도 모르고 넘어갔을 생각을 하니 아찔했다.

 

각설하고 이제 어떻게 풀었는지 설명을 해보겠다.

우선 난 캐시를 ArrayDeque를 이용해 큐로 생각했다.

왜냐면 LRU 삭제할 대상 선정에 대해 생각을 못했을때 짰기때문..ㅎ
(사실 HashSet으로 하는게 더 나을듯)

동작은 cities의 원소(전부 대문자로 바꿔준)를 하나씩 순회하면서
만약 캐시에 포함되어 있다면 hit했다는 뜻이므로 answer++; 없는 경우에는 일단 +5를 해주고

만약 캐시에 없다면 여기 두 경우로 나뉜다.

• 캐시를 하나 비우고 넣어줘야하는 경우
• 빈칸이 있어서 그냥 넣어도 되는 경우

빈칸이 있어서 그냥 넣어도 되는 경우는 단순히 넣기만 하면 끝이다.

그러나 캐시를 하나 비워야 하는 경우는 말이 다른데
여기서 중요한 최근에 사용되었는 지에 대해서 알아내는 방식은 이렇다.

 

HashMap을 사용해서 cities를 순회하는 반복문 제일 끝
(즉 hit miss 판단 전부하고 넣거나 빼거나 모든 동작끝냈을때)
-> map에 해당 순서를 저장
-> cache에서 빼줄 대상을 물색하여 빼줌

 

빼줄 대상 선정방법은 이러하다.
캐시에 든 city의 순서와 이름을 Node에 넣어서 우선순위큐에 넣어주고
order순으로 정렬한다음 poll하면 order가 가장 작은 city (가장 최근에 사용되지 않았던) 의 이름을 remove 해주면 된다.

정답 코드

import java.util.*;
class Solution {
    static class Node{
        String city;
        int order;
        public Node(String city, int order){
            this.city = city;
            this.order = order;
        }
    }
    public int solution(int cacheSize, String[] cities) {
        ArrayDeque<String> cache = new ArrayDeque<>();
        HashMap<String, Integer> map = new HashMap<>();
        int answer = 0;
        for(int i=0; i<cities.length; i++){
            String x =cities[i].toUpperCase();
            if(cache.contains(x)){
                answer++;
            }
            else{//비어있거나 없을때
                answer+=5;
                if(cache.size()<cacheSize){//그냥 넣으면 됨
                    cache.addLast(x);
                }
                else if(!cache.isEmpty()){//가득찼다
                    PriorityQueue<Node> pq = new PriorityQueue<Node>(Comparator.comparingInt(o1->o1.order));
                    for(String target: cache){
                        pq.add(new Node(target, map.get(target)));
                    }
                    Node cur = pq.poll();
                    cache.remove(cur.city);
                    cache.addLast(x);
                }
            }
            map.put(x, i);
        }
        return answer;
    }
}
// 큐로 캐시 구현
// 만약 새로운 도시이름이 존재한다면 continue하면서 +1
// 없으면 +5 큐가 다찼다면 poll 해두고 새로 넣어주는 동작까지
// 대소문자 구분 않음
// 그런데 반례발생
// poll할때는 단순히 앞에걸 빼주는 것이 아닌 최근에 사용이 되질않은 도시로 빼줘야함
// HashMap으로 해당 city의 제일 최근순번 기록해주기
// 우선순위큐에 city랑 최근 순번 Node 넣어주고 
// 최근순번 작은 순으로 빼주고 그걸로 삭제해주면 된다.