[프로그래머스/17680] [1차] 캐시 (Java)

Question

2018 KAKAO BLIND RECRUITMENT > [1차] 캐시

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17680
• 분류 : 브루트포스
• 풀이 시간 : 10분

문제 해설

1. 캐시 = 캐시 크기(cacheSize)만큼 용량 잡을 수 있음
2. 도시 이름 배열을 순서대로 처리할 때 캐시에서 검색
   1. 캐시에 해당 도시 이름 존재하면(cache hit) : 실행시간 += 1
   2. 캐시에 해당 도시 이름 존재하지 않으면(cache miss) : 실행시간 += 5
3. 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용
4. 총 실행시간은?

Solution

풀이 접근 방법

1. 캐시 교체 알고리즘은 LRU(Least Recently Used)

   메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신

   1. 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신
   2. 가장 최근에 사용된 항목은 리스트의 맨 앞에 위치
   3. 가장 최근에 사용되지 않은 항목 = 리스트 맨 뒤에 있는 값 순서대로 리스트에서 제거

2. LRU를 구현하기 위해서는 캐시 리스트 안에서 위치 상관 없이(앞, 뒤, 중간 모두 가능) 많은 자료의 삽입과 삭제가 이루어짐

   1. ArrayList 사용 지양
      1. ArrayList = 일반적으로 배열과 같은 순차 리스트 + 인덱스 존재
      2. 중간에 값 들어오면 전체적으로 1씩 뒤로 밀림 → 해당 데이터 이후 모든 데이터 복사됨
   2. Queue 사용 불가
      1. Queue는 선입선출이기 때문에 중간있는 값을 제거할 수 없음
   3. LinkedList 사용!
      1. LinkedList = 양방향 포인터
      2. 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식
      3. 중간에 데이터 추가/삭제 시 앞 뒤 링크만 변함 → 해당 노드의 주소지만 바꾸면 됨

정답 코드

import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList<String> cache = new LinkedList<String>();
        int hit = 1;
        int miss = 5;
        
      	// 캐시 사이즈가 0 = 캐시에 아무것도 못 담음 => 모두 cache miss
        if (cacheSize == 0) 
            return cities.length * miss;
        
        for (String pastCity : cities) {
          	// 대소문자를 구분하지 않기 때문에 모두 소문자로 변환하여 저장
            String city = pastCity.toLowerCase();
            
            if (!cache.isEmpty() && cache.contains(city)) {
                // 가장 최근에 사용된 항목은 리스트의 맨 앞에 위치해야 하기 때문에 캐시 안에 있는 값 미리 삭제
                cache.remove(cache.indexOf(city));
                answer += hit;
            } else {
                // 이미 캐시 최대 사이즈를 도달했다면
                if (cache.size() >= cacheSize) {
                    // 맨 뒤에 있는 값 삭제
                    cache.remove(cacheSize - 1);
                }
                answer += miss;
            }
            // 가장 최근에 조회한 값 맨 앞에 위치
            cache.add(0, city);
        }
        return answer;
    }
}