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

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

프로그래머스

컴퓨터 공학적인 문제처럼 보이지만 카카오는 코테에서 검색이 가능하기에 LRU알고리즘정도는 검색하고나서 구현하면 된다.

 

1트

검색이 가능하고, 순차적 저장이 가능한 데이터타입을 사용해야한다.

데이터 타입을 HashSet과 LinkedList중에 고민하였으나 HashSet은 삭제에서 비효율적일듯해 List로 결정 

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        
        if(cacheSize == 0){
            return cities.length * 5;
        }
        
        int answer = 0;
        
        // 순서가 있어야하고, 검색이 가능한 자료 구조 (처음엔 hashset을 생각함)
        LinkedList<String> cache = new LinkedList<>();
        
        for(int i=0; i<cacheSize; i++){
            cache.add(cities[i].toUpperCase());
            answer+= 5;
        }
        
        // 투포인터?
        for(int j=cacheSize; j<cities.length; j++){
            
            for(int k=0; k<cacheSize; k++){
                if(cache.get(k).equals(cities[j].toUpperCase())){
                    answer+=1;
                    cache.remove(0);
                    cache.add(cities[j].toUpperCase());
                    break;
                }else if(k == cacheSize-1){
                    cache.remove(0);
                    cache.add(cities[j].toUpperCase());
                    answer+= 5;
                }
            }
        }
        
        return answer;
    }
}

 

2트

처음짠 로직으론 커버가 안되는 반례가 많았다.

입력값 〉 5, ["a", "b", "c", "b", "a"]
기댓값 〉 17

이런 케이스

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        
        if(cacheSize == 0){
            return cities.length * 5;
        }
        
        int answer = 0;
        
        // 순서가 있어야하고(인덱스 조회), 검색이 가능한 자료 구조 (처음엔 hashset을 생각함)
        LinkedList<String> cache = new LinkedList<>();
        
        for(int i=0; i<cacheSize; i++){
            if(cache.contains(cities[i].toUpperCase()) == true){
                // System.out.println("중복 저장");
                answer+= 1;
            }else{
                cache.add(cities[i].toUpperCase());
                answer+= 5;
            }
        }
        
        // System.out.println();
        
        // 투포인터?
        for(int j=cacheSize; j<cities.length; j++){
            for(int k=0; k<cacheSize; k++){
                if(cache.get(k).equals(cities[j].toUpperCase())){
                    answer+=1;
                    cache.remove(0);
                    cache.add(cities[j].toUpperCase());
                    break;
                }else if(k == cacheSize-1){
                    cache.remove(0);
                    cache.add(cities[j].toUpperCase());
                    answer+= 5;
                }
            }
        }
        
        return answer;
    }
}

 

이렇게해도 9, 11, 15, 16,18,19,20번에서 뭔가 자꾸 틀리길래 모범답안과 비교하여 GPT에게 뭘 개선해야하냐고 물어봤다

캐시 초기화: 첫 번째 코드에서는 cacheSize가 캐시의 최대 크기로 사용되며, 캐시가 이 크기를 초과할 경우 가장 오래된 요소를 삭제합니다. 두 번째 코드에서는 초기에 cacheSize만큼의 요소를 캐시에 추가하려고 시도하지만, 중복 체크를 통해 중복이 없을 경우에만 캐시에 추가합니다. 이는 캐시가 cacheSize보다 작을 수 있음을 의미합니다. 처리 로직: 첫 번째 코드는 모든 도시를 소문자로 변환하여 처리합니다. 이는 대소문자를 구분하지 않는 캐시 정책을 의미합니다. 두 번째 코드는 대문자로 변환하여 처리합니다. 또한, 두 번째 코드에서는 첫 cacheSize 요소에 대한 처리가 첫 번째 요소부터 시작되지만, 중복 검사를 통해 실제로 캐시에 추가되지 않을 수도 있습니다. 중복 처리: 첫 번째 코드에서는 중복된 요소를 발견할 경우 해당 요소를 캐시에서 제거한 후, 다시 캐시의 끝에 추가합니다. 이는 캐시에서 가장 최근에 사용된 요소가 캐시의 끝에 위치하도록 함으로써 LRU (Least Recently Used) 캐시 정책을 구현합니다. 두 번째 코드에서도 같은 LRU 캐시 정책을 사용하지만, 캐시 초기화 방식의 차이로 인해 동작이 달라질 수 있습니다. 효율성: 첫 번째 코드는 효율적으로 작성되었습니다. contains 메소드와 remove 메소드를 사용하여 중복 검사와 요소 삭제를 수행합니다. 두 번째 코드는 투 포인터 방식을 사용하여 캐시를 관리합니다. 하지만 이 방식은 cacheSize가 클 경우 비효율적일 수 있으며, LinkedList의 get 메소드가 인덱스에 기반한 접근을 사용하기 때문에 O(n)의 시간 복잡도를 가집니다.

 

이렇게 최종 코드

2중 for문을 contains 메소드를 사용해 정리하였다.

public int solution(int cacheSize, String[] cities) {
    if (cacheSize == 0) {
        return cities.length * 5;
    }

    int answer = 0;
    LinkedList<String> cache = new LinkedList<>();

    for (String city : cities) {
        String formattedCity = city.toLowerCase(); // 도시 이름을 소문자로 변환

        // 캐시에 도시가 이미 존재하는 경우
        if (cache.contains(formattedCity)) {
            cache.remove(formattedCity); // 캐시에서 해당 도시 삭제
            cache.addLast(formattedCity); // 캐시의 끝에 다시 추가
            answer += 1; // 캐시 히트
        } else {
            // 캐시가 가득 차 있을 경우, 가장 오래된 요소를 삭제
            if (cache.size() == cacheSize) {
                cache.removeFirst();
            }
            cache.addLast(formattedCity); // 새 도시를 캐시의 끝에 추가
            answer += 5; // 캐시 미스
        }
    }
    
    return answer;
}

 

---

 

LRU 알고리즘이란?

https://dailylifeofdeveloper.tistory.com/355

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법