[프로그래머스/Programmers] [1차] 캐시 (Java - LRU - Level2)

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

---

⭐️ 코드

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0; // 캐시 hit, miss 누적 값
        LinkedList<String> linkedList = new LinkedList<String>(); // queue 구현체
        for (int i = 0; i < cities.length; i++) {
            // 캐시에 들어갈 값 소문자화 시키기
            String lowercaseCity = cities[i].toLowerCase(Locale.ROOT);
            // 캐시 사이즈가 0인 경우
            if(cacheSize == 0) {
                return 5*cities.length;
            }
            // 캐시에 값이 있는 경우 hit
            if (linkedList.remove(lowercaseCity)) {
                linkedList.add(lowercaseCity);
                answer += 1;
            }
            // 캐시에 값이 없는 경우 miss
            else {
                if(linkedList.size() < cacheSize) {
                    linkedList.add(lowercaseCity);
                    answer += 5;
                    continue;
                }
                else if (linkedList.size() == cacheSize) {
                    linkedList.removeFirst();
                    linkedList.add(lowercaseCity);
                    answer += 5;
                }
            }
        }
        return answer;
    }
}

---

💡 문제 풀이

처음에는 LRU(Least Recently Used)라는 알고리즘이 뭔지 잘 몰랐다.  구글링을 통해 알아보니 LRU는 가장 최근에 쓰이지 않은 친구를 삭제하고 새로운 친구를 데려오는 방식이다.

구현은 Queue 방식과 비슷하다고 생각이 들었고 추가적인 구글링을 통해 큐로도 푸는 방법이 있다는 것을 알게 되었다. 

 

하지만 아직 큐에 대해서는 잘 모르기 때문에 LinkedList를 활용해서 문제를 풀어보도록 할 것이다.

 

먼저 문제를 보게 되면 캐시가 무엇인지 궁금할 것이다. 

캐시는 CPU 메모리 중 가장 비싸고 속도가 빠르고 용량이 적어서 많은 메모리를 담지 못한다. 하지만 메모리를 미리 기억해 두기 때문에 속도가 빠르다. 아무튼 여기까지만 알아보자. 더 궁금하면 구글링 하자.

 

내가 잘 모르겠던 것은 cache hit과 cache miss였는데 cache hit은 캐시에 미리 값이 저장되어 있는 경우고, cache miss는 캐시에 데이터가 없어 새로 저장하거나 삭제하고 다시 입력하는 경우를 말한다. 캐시 미스와 캐시 히트의 정확한 정의는 구글링을 해서 알아보자.

 

결국 캐시 메모리에 값이 미리 있는 경우에는 +1, 값이 없거나 새로 입력하고 삭제하는 경우에는 +5를 하면 되는 문제다.

 

내가 LinkedList를 사용하는 이유는 값을 추가하면 가장 뒤쪽에 추가가 되고, 데이터를 삭제하고 추가하는 속도가 배열보다 빠르기 때문이다.

 

for (int i = 0; i < cities.length; i++) {
    // 캐시에 들어갈 값 소문자화 시키기
    String lowercaseCity = cities[i].toLowerCase(Locale.ROOT);
    // 캐시 사이즈가 0인 경우
    if(cacheSize == 0) {
        return 5*cities.length;
    }

먼저 포문을 통해 값을 입력하게 될 것인데 여기서 두 가지 알아야 될 점이 있다. 

1. 캐시 size가 0인 경우
2. 캐시에 들어가는 데이터는 대소문자가 구분 없는 알파벳이다.

이런 제한사항과 case를 생각하지 않는다면 여러분은 테스트 5번과 6번을 실패하게 될 것이다.

나는 캐시 메모리에 들어가는 데이터의 중복 값을 막기 위해 모든 cities 배열의 값을 소문자화 해서 풀었다.(대문자로 해도 상관없다)

또한 캐시 사이즈가 0인 경우에는 cities []의 길이만큼 cache miss가 발생한다. 따라서 실행 시간은 cache miss * cities.length가 될 것이다.

위 두 조건을 먼저 작성한 다음 아래를 풀어보자.

 

// 캐시에 값이 있는 경우 hit
if (linkedList.remove(lowercaseCity)) {
    linkedList.add(lowercaseCity);
    answer += 1;
}
// 캐시에 값이 없는 경우 miss
else {
    if(linkedList.size() < cacheSize) {
        linkedList.add(lowercaseCity);
        answer += 5;
        continue;
    }
    else if (linkedList.size() == cacheSize) {
        linkedList.removeFirst();
        linkedList.add(lowercaseCity);
        answer += 5;
    }
}

 조건을 크게 두 가지로 나누고, 캐시에 값이 없는 경우에는 추가적으로 분할을 해줬다.

캐시에 값이 있는 경우에는 같은 값이 들어오면 remove 함수가 실행될 것이고, remove 함수가 실행된다는 건 당연히 값이 있다는 뜻일 테니까 조건을 위처럼 작성했고 cache hit에 해당하는 +1 값을 추가해 줬고

 

캐시에 값이 없는 경우에는 리스트의 크기가 캐시 사이즈보다 작을 경우에는 계속 추가를 해주고, 리스트의 사이즈와 캐시 사이즈가 같다면 가장 뒤에 있는 하나를 지우고, 새로 들어오는 데이터를 삽입하면 맨 뒤에 삽입이 될 테니 문제가 제공하는 형태로 풀 수 있다.

 

하지만 뭔가 이상하다고 느끼긴 했다..

 

이게 맞... 나..?

 

캐시 데이터를 삭제하고 새로 집어넣는 게 문제가 풀라고 하는 형식과 다른데... 캐시에서 이동하는 거랑은 다른데...

일단 이렇게 풀었고 문제 해설은 나중에 멋있는 형님께 물어보도록 하겠다!

 

DLL, Queue, LinkedHashSet 방법으로 나중에 한번 더 풀어볼 생각이다

---

👀 후기

쉽긴 쉬운데...

이게.. 맞나...?

도와줘요 코테 요정님🥲