코테 연습[자바 코테 준비 10일차] , LinkedHashSet

2018 카카오 블라인드 문제  1차 캐시 문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java 

프로그래머스

처음 문제를 봤을때는 으잉 ? 했다.

cache hit, miss 의 관한 개념과 LRU 의 관하여 몰랐기 때문이다.

 

이 문제를 해결하기 위한 기초 개념을 설명한 글이 포함된 블로그를 첨부한다. 

https://chanhuiseok.github.io/posts/prog-3/

[2018 KAKAO BLIND RECRUITMENT] [1차] 캐시

 

 

cache miss 를 유발하는 마지막테게를 참고하자.

cache size = 0 즉 cache 가 없다면  주어진 데이터의 원소들의 개수 * 5 를 해준다.

 

// 캐시의 동작을 안다면 간단한구현으로 될것이며 ,

문제 조건 사항중 대소문자를 구분하지 않는다는 조건을 사전에 잘  캐치하면 좋을 것 같다 .  + 알맞은 자료구조를 사용하는 문제이다

   void test_cache_sol() {
        String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};
        int cacheSize  = 2 ;
        System.out.println(solution2(cacheSize,cities));
    }
    public int solution2(int cacheSize, String[] cities) {
        for(int i = 0 ; i<cities.length;i++) {
            cities[i] =cities[i].toUpperCase();
        }


        int operationTime=0 ;
        if(cacheSize == 0 ){
             // no cache and all  cache miss
            return cities.length * 5 ;
        }

        List<String> fastList = new ArrayList<>();
        int check = 0  ;
        for(String city:cities){
            if(fastList.contains(city)){
                check =1 ;
                break;
            }
            else {
                fastList.add(city);
            }
        }

        if(check == 0){
            return cities.length * 5 ;
        }

        // Hash  ?  hash 의 사이즈를 비교
        // name  , recentUsed Info
        // vlaue : recently call point
        Map<String,Integer> cache = new HashMap<>();
        // What  is proper DS  ?  , need  key value , pop out Least Recently Used

        for(String city : cities) {
            if(cache.size() == 0 ){
                operationTime += 5;
                cache.put(city,0);
                continue;
            }
            if(cache.containsKey(city)) {
                operationTime += 1;
                for(Map.Entry<String,Integer> entry : cache.entrySet()) {
                        cache.put(entry.getKey(),entry.getValue()+1);
                    }

                cache.put(city,0);
            }
            else{
                operationTime += 5;
                if(cache.size() >= cacheSize) {
                    int maxValue = cacheSize;
                    String oldKey = "";
                    for(Map.Entry<String,Integer> entry : cache.entrySet()){
                        if (entry.getValue() == maxValue-1) {
                            oldKey =  entry.getKey();
                        }
                        else{
                            cache.put(entry.getKey(),entry.getValue()+1);
                        }
                    }
                    cache.remove(oldKey);
                }
                else{
                    for(Map.Entry<String,Integer> entry : cache.entrySet()){
                        cache.put(entry.getKey(),entry.getValue()+1);
                    }
                }
                cache.put(city,0);
            }
        }

        return  operationTime;
    }
}

 

 

--- 위와 같은 코드를 한번 최적화 시켜 보자.

 

cache 를  중복이 불가능 하며 넣는 순서를 유지하는 LinkedHashSet 을 이용하여 구현한다.

 

 

String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};

 

다음과 같이 주어진다면 , 캐시가 3 이라는 사이즈일때



cache.add(city) 를 할시 배열의 뒤에서 부터 들어 간다라고 이해를 하면 된다. 

 

자연스럽게 가장 오래된 , 먼저 넣은 도시는 0 번 인덱스를 유지하고 있다. 

 

 

1. 만약 캐시에 맞는 도시가 있다면 즉 cache hit 인 경우는 도시를 지우고 다시 넣으면 된다.

if (cache.contains(city)) {
    operationTime += 1;
    cache.remove(city);
    cache.add(city);

 

 

2. 캐시가 꽉 찬 경우 가장 앞에 있는 원소를 지워준다. 

if (cache.size() >= cacheSize) {
    Iterator<String> iterator = cache.iterator();
    iterator.next();
    iterator.remove();
}

 

전체 코드

 

public int sol2_optimal(int cacheSize,String[] cities){
    if (cities.length == 1)
        return 5;

    for (int i = 0; i < cities.length; i++) {
        cities[i] = cities[i].toUpperCase();
    }

    int operationTime = 0;

    if (cacheSize == 0) {
        return cities.length * 5;
    }

    Set<String> cache = new LinkedHashSet<>(cacheSize);
    for (String city : cities) {
        if (cache.contains(city)) {
            operationTime += 1;
            cache.remove(city);
            cache.add(city);
        } else {
            operationTime += 5;
            if (cache.size() >= cacheSize) {
                Iterator<String> iterator = cache.iterator();
                iterator.next();
                iterator.remove();
            }
            cache.add(city);
        }
    }

    return operationTime;
}