캐시

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

시간을 두고 총 3번 문제를 풀었습니다.
효율성 면에서는 3회차 > 1회차 > 2회차 가 가장 좋았으며
삽입과 삭제 면에서 뛰어난 LinkedList를 실제로 사용해볼 수 있어 좋았습니다..!

문제설명

• 주어진 파라미터: int cacheSize, String[] cities
• 반환값: int
• cities를 순회하며 cacheSize만큼 캐시 저장한 뒤, LRU 방식에 맞게 실행시간 측정
• 캐시 히트: 1 / 캐시 미스: 5

풀이방식

1. Queue를 이용해서 캐시 구현
2. LRU 방식에 맞게 Queue 내에 있을 경우 해당 요소만 빼고 맨 뒤 삽입
   (1회차) Queue 1개 사용, 총 4가지 경우의 수(q내에 있는 경우, 없는 경우 + 캐시 사이즈 초과 / 미만)
   (2회차) Queue 1개, List 1개 사용, Queue를 통해 contains를 확인할 수 있었지만.. 그러지 않고 굳이 List 사용
   (3회차) LinkedList 1개 → 중간 삭제면에서 가장 뛰어난 속도를 보여줌

코드

• 1회차
  Queue 1개 사용
  총 4가지 경우의 수(q내에 있는 경우, 없는 경우 + 캐시 사이즈 초과 / 미만)

/*
1. 없다 -> q 개수 x / q 개수 o
2. 있다 ->
*/
import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        Queue<String> q = new ArrayDeque<>();
        int answer = 0;
        
        if (cacheSize == 0) return cities.length * 5;
        
        for(int i = 0; i < cities.length; i++){
            String c = cities[i].toLowerCase();
            
            if(!q.contains(c)){
                if(q.size() < cacheSize){
                    q.offer(c);
                }else{
                    q.poll();
                    q.offer(c);
                }
                
                answer += 5;
            }else{
                if(q.size() < cacheSize){
                    int len = q.size();
                    for(int j = 0; j < len; j++){
                        String cur = q.poll();
                        if(cur.equals(c)) continue;
                        q.offer(cur);
                    }
                    q.offer(c);
                }else{
                    for(int j = 0; j < cacheSize; j++){
                        String cur = q.poll();
                        if(cur.equals(c)) continue;
                        q.offer(cur);
                    }
                    q.offer(c);
                }
                
                answer += 1;
            }
        }
        
        return answer;
    }
}

• 2회차
  Queue 1개, List 1개 사용
  Queue를 통해 contains를 확인할 수 있었지만.. 그러지 않고 굳이 List 사용

import java.util.*;
// Queue, ArrayList -> queue안에 있는지 확인 

class Solution {
    public int solution(int cacheSize, String[] cities) {
        ArrayList<String> list = new ArrayList<>();
        ArrayDeque<String> queue = new ArrayDeque<>();
        int playTime = 0;
        
        if(cacheSize == 0 ) return cities.length * 5;
        
        for(String city : cities ){
            city = city.toLowerCase();
            
            if(list.size() < cacheSize){
               // 캐시가 차지 않았을 때 
                if(list.contains(city)){
                    // 캐시에 있을 경우 
                    ArrayDeque<String> stack = new ArrayDeque<>();
                    while(!queue.peekFirst().equals(city)){
                        stack.push(queue.poll());
                    }
                    
                    queue.poll();
                    while(!stack.isEmpty()){
                        queue.addFirst(stack.pop());
                    }
                    queue.offer(city);
                    playTime += 1;
                }else{
                    // 캐시에 없을 경우 
                    queue.offer(city);
                    list.add(city);
                    playTime += 5;
                }
                
            }else if(list.size() >= cacheSize){

                // 캐시 가득 찬 경우 
                // 캐시 내 있는 경우 
                if(list.contains(city)){
                    ArrayDeque<String> stack = new ArrayDeque<>();
                    while(!queue.peekFirst().equals(city)){
                        stack.push(queue.poll());
                    }
                    
                    queue.poll();
                    while(!stack.isEmpty()){
                        queue.addFirst(stack.pop());
                    }
                    queue.offer(city);
                    playTime += 1;
                    
                }else{
                    // 캐시 내 없는 경우 
                    String deleteCity = queue.poll();
                    list.remove(deleteCity);
                    queue.offer(city);
                    list.add(city);
                    playTime += 5;
                }
            }
        }
        
        return playTime;
    }
}

• 3회차

LinkedList 1개
중간 요소 삭제 면에서 가장 뛰어난 속도를 보여줌

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        LinkedList<String> list = new LinkedList<>();
        int playTime = 0;
        
        if(cacheSize == 0) return cities.length * 5;
        
        for(String city : cities){
            city = city.toLowerCase();
            
            if(list.remove(city)){
                playTime += 1;
            }else{
                if(cacheSize == list.size()) list.removeFirst();
                playTime += 5;
            }
            
            list.addLast(city);
        }
        
        return playTime;
    }
}

---

시간을 두고 총 3번 문제를 풀었습니다.
효율성 면에서는 3회차 > 1회차 > 2회차 가 가장 좋았으며
삽입과 삭제 면에서 뛰어난 LinkedList를 실제로 사용해볼 수 있어 좋았습니다..!