코딩테스트 연습 > [1차] 캐시 - JAVA

 

 

풀이 - 나의 생각

중요한 점

 

1. 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

 

2. Cache Size가 0일 경우가 있다.

 

3. 대 소문자 구분이 없다.

 

처음에 문제를 이해하는데 좀 시간이 걸렸다....

 

1. 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다. 에 대해 생각해봅시다.

 

LRU가 뭐지? 라고 생각했다가

 

단어를 보니 대충

 

아 최근에 사용한 것들을 캐시에 넣어놓는 방법이겠다

 

라고 생각했고

 

주어지는 cache size는

 

저장하는 캐시의 최대 개수겠다고 생각했다.

 

그래서 이 생각을 토대로 주어진

 

test case를 풀어보니 정답이 나와서 그렇게 풀었다.

 

즉. LRU는 최근 사용된 것을 캐시에 저장한다.

 

저장할 수 있는 캐시의 개수는 cache size

 

새로운 것이 들어올때는 가장 처음에 들어온 것을 내보낸다.

 

cache hit 은 새로 들어오려는 게 이미 캐시에 있는 경우

 

cache miss 는 없는 경우이다.

 

2. Cache Size가 0일 경우

 

캐시의 사이즈가

 

주어진 cache size 를 넘어가는 경우(같은 경우로 해도 됨)와

 

넘어가지 않는 경우에 따라

 

처리하는 방식이 다른데

 

cache size를 넘어가는 경우

 

캐시의 맨 앞의 것을 삭제하고

 

새로운 것을 뒤로 넣어야 한다.

 

그런데

 

주어진 cache size가 0일 경우

 

캐시에 들어있는 것도 없는데

 

삭제를 하려고 해서 에러가 난다.

 

그러니까 cache size가 0일 경우를

 

예외처리 해줘야 한다.

 

3. 대소문자 구분이 없다

 

그냥 toUpperCase() or toLowerCase()를 사용하면 끝

 

 

기타

 

이 문제는 2017년 카카오 코테에서

 

3번으로 나와, 정답률 45.26%를 기록한 문제이다.

 

문제의 난이도가 그렇게 높지 않은데도

 

정답률이 낮은 이유는

 

LRU, cache hit, cache miss 와 같은 용어에 익숙하지 않았서

 

문제를 이해하는데 어려움을 겪었기 때문이지 않을까 생각한다.

 

 

 

코드

 

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        List<String> lru = new ArrayList<>();
        /*
        캐시에 있어?
        Yes -> 캐시 안의 도시 삭제, 맨 끝으로 입력 = cash hit = 1
        No -> cash miss = 5
        List size가 cache size를 넘어가?
        Yes -> 가장 맨 앞의 도시 삭제, 맨 끝에 새로운 도시 입력
        No -> 그냥 추가
        */
        if(cacheSize == 0) return 5*cities.length;
        for(String name : cities){
            String city = name.toUpperCase();
            if(lru.contains(city)){
                answer+=1;
                lru.remove(city);
                lru.add(city);
            }else{
                answer+=5;
                if(lru.size() >= cacheSize){
                    lru.remove(0);
                    lru.add(city);   
                }else{
                    lru.add(city);   
                }
            }
        }
        return answer;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요