[프로그래머스] level2. [1차] 캐시 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. [1차] 캐시 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17680

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

---

# 접근 방법 및 풀이 

 

• 먼저 캐시교체알고리즘 LRU와 cache hit, cache miss가 무엇인지 알아야한다.
• 아래 블로그에 설명이 잘 나와있다.
• https://m.blog.naver.com/tlstjd436/221824813403
• LRU를 구현하기 위해 Queue를 쓰는 사람도 있고 그냥 ArrayList를 사용한 사람도있다.
• 나는 LinkedList로 구현했다.
• 생각보다 문제만 잘 이해하고 있으면 구현하는 것은 쉬웠다. 
• 중요한건 cacheSize가 0일때 처리를 해주어야한다. 카카오 블로그에서 보니까 이 문제 정답률이 40프로대였다.
• 0일때 처리를 해주지 않아서 정답률이 많이 낮아진 것 같다. 역시 문제를 정확히 읽어야 한다..
• 이번에 알게된건 remove()메소드이다. 단순히 remove(int index)만 있는 줄 알았다. 리스트에 해당 인덱스 정수를 넣으면 그 인덱스번째의 값이 지워지는 것만 알고있었는데 새로운걸 알게됐다!
• remove(Object object) 파라미터에 Class형태의 값 자체를 넘기면 해당 값을 지워버리고 boolean을 반환한다.
• 해당 값이 없다면 false, 있다면 지우고 true를 반환하는 것이다.
• LinkedList<String> list = new LinkedList<>();
• list.add("a");
• list.add("b");
• list.add("c");
• 이렇게 했을 경우 list.remove("b")를 하면 b가 지워지고 list엔 ["a", "c"] 이렇게 남는다.
• 이 remove()메소드는 LinkedList뿐만 아니라 ArrayList에도 있다.
• cache hit일 경우 해당 단어를 찾아서 지워야하는지 고민했는데 저 remove()를 쓰면 간단히 지워진다.
• 자세한건 코드참조

# 주의할 점 

 

• cacheSize 0일때 확인하기!

 

JAVA 코드

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0)
            return cities.length*5;
        
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();
        for(int i = 0; i < cities.length; i++){
            String s = cities[i].toUpperCase();
            if(cache.remove(s)){
                answer += 1;
                cache.add(s);
            }else{
                answer += 5;
                if(cache.size() >= cacheSize){
                    cache.remove(0);
                }
                cache.add(s);
            }
        }
        return answer;
    }
}

 

 

 

REVIEW