1차 캐시→ 익명 클래스★★, this참조변수, super() 생성자

익명클래스가 있는 경우-시간초과로 인한 실패

import java.util.*;
public class Solution {
    public static int solution(int cacheSize, String[] cities) {
        // city가 cache에 없는 경우에는 전부다 cache miss이다.
        if (cacheSize == 0) {
            return cities.length * 5;
        }

        // cities의 요소를 저장하기 위한 cache공간으로 LinkedHashMap을 사용한다.(익명객체)
        Map<String, String> cache = new LinkedHashMap<String, String>(cacheSize, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return this.size() > cacheSize;
            }
        };

        // 최초실행시간을 0으로 초기화한다.
        int executionTime = 0;

        // 대소문자를 구분하지 않으므로 전부다 대문자로 바꾸어 놓는다.
        for (String city : cities) {
            city = city.toUpperCase();

            // 만약에 city가 cache안에 있다면 cache hit이다.
            if (cache.containsKey(city)) {
                executionTime += 1;
            }
            // city가 cache안에 없는 경우: 애당초 없었던 경우, 꽉차서 없었던 경우
            else {
                executionTime += 5;
                // city는 key이고 null은 value이다.
                cache.put(city, "None");
            }
        }

        return executionTime;
    }
}

 

 

 

 

익명클래스를 별도로 분리한 경우-시간 초과로 실패 

import java.util.*;
public class Solution {
    public static int solution(int cacheSize, String[] cities) {
        // city가 cache에 없는 경우에는 전부다 cache miss이다.
        if (cacheSize == 0) {
            return cities.length * 5;
        }

        // cities의 요소를 저장하기 위한 cache공간으로 LinkedHashMap을 사용한다.
        Map<String, String> cache = new MyLinkedHashMap(cacheSize);

        // 최초실행시간을 0으로 초기화한다.
        int executionTime = 0;

        // 대소문자를 구분하지 않으므로 전부다 대문자로 바꾸어 놓는다.
        for (String city : cities) {
            city = city.toUpperCase();

            // 만약에 city가 cache안에 있다면 cache hit이다.
            if (cache.containsKey(city)) {
                executionTime += 1;
            }
            // city가 cache안에 없는 경우: 애당초 없었던 경우, 꽉차서 없었던 경우
            else {
                executionTime += 5;
                // city는 key이고 null은 value이다.
                cache.put(city, "None");
            }
        }

        return executionTime;
    }
}

class MyLinkedHashMap extends LinkedHashMap<String, String> {
    private int cacheSize;

    public MyLinkedHashMap(int cacheSize) {
        super(cacheSize, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return this.size() > cacheSize;
    }
}

 

 

 

MyLinkedHashMap의 조상인 LinkedHashMap에 있는 생성자의 형태 

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

 

 

 

LinkedHashMap조상인 HashMap에 있는 생성자의 형태 

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

 

해설 

▶MyLinkedHashMap 클래스는 LinkedHashMap을 상속받고 있고, LinkedHashMap의 생성자를 호출하고 있습니다. 

 

즉, MyLinkedHashMap 클래스의 생성자에서는 super(cacheSize, 0.75f)로 LinkedHashMap 생성자를 호출하고 있습니다.

▶LinkedHashMap 생성자는 인자로 전달받은 initialCapacity와 loadFactor를 이용해 HashMap의 생성자를 호출합니다. 

그러면 HashMap의 생성자는 LinkedHashMap으로부터 받은 인자인 initialCapacity와 loadFactor를 이용해

HashMap 객체를 생성하고, LinkedHashMap은 이를 상속받습니다.

▶MyLinkedHashMap 클래스에서는 LinkedHashMap의 removeEldestEntry 메소드를 재정의하고 있습니다. 

   이 메소드는 LinkedHashMap에 새로운 값이 추가될 때(cache.put)마다 호출되는 메소드로,

   이 메소드가 true를 반환하면 LinkedHashMap에서 가장 오래된 값을 삭제합니다.

▶ MyLinkedHashMap 클래스에서는 removeEldestEntry 메소드에서

    MyLinkedHashMap size()가 cacheSize보다 크면 true를, 그렇지 않으면 false를 반환하게 구현하고 있습니다.

 

 

▶ 따라서 removeEldestEntry 메소드에서 size() > cacheSize를 반환하면, 맵의 크기(size)가 cacheSize보다 크면

    가장 오랫동안 사용되지 않은 요소를 제거하라고 LinkedHashMap에 알려줍니다. 

 

 

 

오답임

import java.util.*;


public class Solution2 {
    public static int solution(int cacheSize, String[] cities) {
        // city가 cache에 없는 경우에는 전부다 cache miss이다.
        if (cacheSize == 0) {
            return cities.length * 5;
        }

        // cities의 요소를 저장하기 위한 cache공간으로 LinkedHashMap을 사용한다.
        Map<String, String> cache = MyLinkedHashMap.newInstance(cacheSize);

        // 최초실행시간을 0으로 초기화한다.
        int executionTime = 0;

        // 대소문자를 구분하지 않으므로 전부다 대문자로 바꾸어 놓는다.
        for (String city : cities) {
            city = city.toUpperCase();

            // 만약에 city가 cache안에 있다면 cache hit이다.
            if (cache.containsKey(city)) {
                executionTime += 1;
            }
            // city가 cache안에 없는 경우: 애당초 없었던 경우, 꽉차서 없었던 경우
            else {
                executionTime += 5;
                // city는 key이고 null은 value이다.
                cache.put(city, "None");
                Set<Map.Entry<String, String>> x = cache.entrySet();
                System.out.println(x);
            }
        }

        return executionTime;
    }

    public static void main(String[] args) {
        Solution2 s = new Solution2();
        int cacheSize =3;
        String[] cities={"Seoul", "Ulsan", "Busan", "Ulsan","Seoul"};

        System.out.println(solution(cacheSize, cities));
    }
}

class MyLinkedHashMap<K, V> extends LinkedHashMap<String, String> {
    private int cacheSize;

    public MyLinkedHashMap(int cacheSize) {
        super(cacheSize, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    public static<K,V> MyLinkedHashMap<String, String> newInstance(int cacheSize) {
        return new MyLinkedHashMap<String, String>(cacheSize);

    }


    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return this.size() > cacheSize;
    }


}

 

 

 

최종적인 정답 → cache에 존재해도 지우고, 없어도 지우고

import java.util.ArrayList;

class Solution {
    public static int solution(int cacheSize, String[] cities) {
        int answer = 0;
        ArrayList<String> list = new ArrayList<String>();

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

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

            if (list.contains(cities[i])) {
                answer++;
                list.remove(cities[i]);
                list.add(cities[i]);
            } else {
                answer += 5;
                if (list.size() == cacheSize) {
                    list.remove(0);
                    list.add(cities[i]);
                }
                else 
                    list.add(cities[i]);
            }
        }
        return answer;
    }
}