프로그래머스 - 17680번: [1차] 캐시 [Java]

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue <String> cache = new LinkedList<>();
        for(String s : cities) {
            s = s.toLowerCase();
            if(cache.contains(s)) {
                answer++;
                cache.remove(s);
                cache.offer(s);
            }
            else {
                answer += 5;
                if(cache.size() == cacheSize)
                    cache.poll();
                if(cache.size() < cacheSize)
                    cache.offer(s);
            }
        }
        return answer;
    }
}

2. 설명

캐시 메모리에 임의의 데이터를 요청할 때 해당 데이터가 존재한다면 캐시 적중(cache hit)이며 1초가 걸린 것으로 가정하고, 해당 데이터가 존재하지 않는 것을 캐시 부적중(cache miss)이며 5초가 소요됩니다.
캐시 메모리의 데이터 교체 방식은 Least Recently Used은 가장 오랫동안 참조하지 않은 데이터를 위주로 교체를 한다는 것입니다.
위 이야기를 알게되면 문제는 이제 쉽게 해결됩니다.

s = s.toLowerCase();
if(cache.contains(s)) {
    answer++;
    cache.remove(s);
    cache.offer(s);
}

도시의 이름은 대소문자 상관이 없기에 임의로 소문자로 통일하여 활용됩니다. cache에 존재하는지 확인 후 있다면 cache hit이기에 answer에서 1증가하고 cache에 저장된 데이터를 제일 마지막 위치로 저장합니다.

else {
    answer += 5;
    if(cache.size() == cacheSize)
        cache.poll();
    if(cache.size() < cacheSize)
        cache.offer(s);
}

만약 cache 내에 존재하지 않으면 cache miss이기에 answer에 5증가를 한 뒤 현재 cahe에 저장된 수와 제한된 수가 동일하다면 cache 내의 데이터를 제거하며 제한된 수보다 작다면 추가를 해줍니다. 제한된 수가 0일 수도 있기에 0일 때는 추가되지 않게 합니다.

3. 정리

1. 캐시 적중(cache hit), 캐시 부적중(cache miss), LRU(Least Recently Used)에 대한 개념 필요
2. Queue를 이용해 구현

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges