[프로그래머스/Lv. 2] [1차] 캐시 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public int solution(int cacheSize, String[] cities) {
 
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();
        
        // 캐시 사이즈가 0인 경우 특수처리
        if(cacheSize == 0)
            return 5 * cities.length;
        
        
        for(int i = 0 ; i < cities.length ; i++) {
            String city = cities[i].toLowerCase();
            
            // [cache hit]
            if(cache.remove(city)) {    // 기존 페이지 지우고,
                cache.addFirst(city);   // 이미 캐시에 있던 페이지 맨 앞으로 가져옴.
                answer += 1;
            }
            else {  // [cache miss]
               int nowSize = cache.size();
                
                if(nowSize == cacheSize) {  // 캐시가 가득찬 경우, 맨 뒤 페이지 삭제
                    cache.pollLast();   // = remove(0)
                }
                
                cache.addFirst(city);   // 맨 앞에 새 페이지 삽입
                answer += 5;
            }
        }
        
        return answer;
    }
}

 

 

🧩  해결 아이디어

• 단순구현 & *LRU

(* LRU : 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체)

 

- 캐시 사이즈가 0인 경우, 모든 경우에 캐시 미스가 발생하므로 특수처리한다. (5 * 캐시사이즈)

- 0이 아닌 경우, cache hit과 cache miss로 나눠 생각한다.

    ㄴ cache hit인     경우)  이미 캐시 리스트에 기존 페이지가 존재한다면 기존 페이지를 지우고, 이미 캐시에 있던 페이지를 맨 앞에 추가한다. & 정답 + 1

    ㄴ cache miss인 경우) 캐시 리스트가 가득찬 경우, 맨 뒤 페이지를 삭제하고, 맨 앞에 새 페이지를 삽입한다. & 정답 + 5

 

 

 

---

🔺 다른 풀이들

- 복습은 이걸로 해야겠다... 과정은 같고 그냥 리스트를 활용하셨다.

& cache hit인지 확인하기 위해 cache.contains()를 사용하셨다.

프로그래머스 [1차] 캐시 JAVA

import java.util.ArrayList;

class Solution {
    public static int solution(int cacheSize, String[] cities) {
        int answer = 0;
        ArrayList<String> list = new ArrayList<String>();

        if (cacheSize == 0)
            return cities.length * 5;

        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toUpperCase();

            if (list.contains(cities[i])) {
                answer++;
                list.remove(cities[i]);
                list.add(cities[i]);
            } else {
                answer += 5;
                if (list.size() == cacheSize) {
                    list.remove(0);
                    list.add(cities[i]);
                }
                else 
                    list.add(cities[i]);
            }
        }
        return answer;
    }
}

---

💬 느낀 점

흐 담엔 더 잘 풀장,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 정답 참고

 

[프로그래머스] 캐시 (Java)

 

 

✔ LRU 알고리즘

페이지 교체 알고리즘, LRU 캐시 교체 알고리즘이란? 캐시란?, Cache hit, Cache Miss