▲[201223] 캐시 - 2018 KAKAO BLIND RECRUITMENT

0. 문제유형 : 적절한 자료구조 찾기

1. 문제이해

programmers.co.kr/learn/courses/30/lessons/17680

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

(1) 주요 요구사항

: LRU(Least Recently Used) 알고리즘을 사용했을 때 cache hit, cache miss에 따른 실행시간 측정

<LRU(Least Recently Used) 알고리즘>
: cache miss가 발생했을 때 가장 참조된지 오래된 요소와 교체

1. cache hit
- cache에 요소가 有 → 참조 시기 변경
2. cache miss
- cache에 요소가 無 & cache가 꽉 찬 경우 : LRU 알고리즘에 의한 교체 대상과 교체
- cache에 요소가 無 & cache에 빈 공간有 : 캐시에 새롭게 넣기

- 캐시 크기(cacheSize)와 도시이름 배열(cities)가 주어짐

- cache hit에는 1, cache miss에는 5의 실행시간이 소요 → 총 실행시간을 answer로!!

ex>

캐시크기(cacheSize)	도시이름(cities)	실행시간
3	[Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA]	50
3	[Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul]	21

 

(2) 제한사항

- cities의 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자이며 대소문자 구분X

   → toLowerCase()

- cacheSize는 정수이며 0 <= cacheSize <= 30

   → [실수 원인] cacheSize가 0일 때에 주의해야 함!! _ 경계값 테스트 꼭 하자!!

 

 

 

2. 전략

(1) 캐시로 쓸 적절한 자료구조 선별

: HashMap<String, Integer>를 사용 (key : 도시 이름, value : 최근 참조 시기)

[이유]

- 해당 도시이름의 존재유무를 바로 찾을 수 있음 - cache.containsKey()

- cache hit 발생 시 참조 시기 갱신이 쉬움. 위치(인덱스) 변경 없이 value를 갱신해주면 됨 - cache.replace(target, i)

※ 단, cache miss 발생 시 교체 대상을 탐색은 쉽지 않다. 순차 탐색을 통해 가장 오래 전 참조된(=value가 가장 작은) 도시를 찾아야 됨!!

 

(2) cache miss의 처리

: 가장 오래 전 참조된 도시이름을 찾아야 된다. 이를 위해 cache HashMap에서 가장 작은 value를 가진 key를 찾는다!!

- keySet의 Iterator객체를 통해 순차적으로 min과 minKey를 갱신

- 탐색이 끝나면 cache.remove(minKey)

- 새로운 요소를 cache.put(target, i)를 통해 넣어준다. 단, cacheSize가 0일 때는 어떤 것도 넣을 수 없음에 주의한다!!

 

 

 

3. 참고사항

(1) 다른 자료구조 활용 : LinkedHashMap override

LinkedHashMap : HashMap이 순서 유지가 불가능하다는 단점을 보완한 자료구조

docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

- 생성자

LinkedHashMap()
LinkedHashMap(int initialCapacity) //최초 크기, loadFactor default 0.75
LinkedHashMap(int initialCapacity, float loadFactor) // 최초크기, loadFactor
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) // 최초크기, loadFactor, ordering mode

- removeEldestEntry() : 가장 put된지 오래된 데이터를 파라미터로 전달하는 메소드

(이미 map에 있는 요소도 put으로 처리)

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) P
	return false;
}

- removeEldestEntry를 override해서 데이터의 삭제조건을 만들어준다.

Map<String, Integer> lru = new LinkedHashMap<String, Integer>(cacheSize, 1, true){
    @Override
    public boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > cacheSize; //size가 더 큰 경우 true를 return해 가장 오래된 데이터를 삭제할 것
    }
};

 

(2) 다른 자료구조 활용 : 큐(LinkedList)

- removeFirstOccurence(cities[i].toLowerCase()) : 해당 요소의 첫 번째 요소를 삭제. 없는 경우에는 false return

- removeFirst : cache miss인 경우 가장 오래된 요소 삭제

 

(3) 다른 자료구조 활용 : ArrayList

- contains(cities[i])로 포함여부도 확인 가능

- remove(cities[i])로 삭제할 수 있음

 

▶ 여러 자료구조의 메소드에 대한 이해 필요!! 내 풀이와 다르게 remove 시 순차 탐색이 필요 없음.

 

(4) cache.size() == 0인 경우

: 미리 5*cities.length로 계산하는 것이 실행시간을 줄일 수 있다!!!

 

 

 

4. 코드

//30분 소요
import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        HashMap<String, Integer> cache = new HashMap<>();
        for(int i = 0; i < cities.length; i++){
            String target = cities[i].toLowerCase();
            if(cache.containsKey(target)){
                cache.replace(target, i);
                answer++;
            }
            else{
                if(cache.size() == cacheSize) {
                    int min = Integer.MAX_VALUE; String minKey = "";
                    Iterator<String> itr = cache.keySet().iterator();
                    while(itr.hasNext()){
                        String next = itr.next();
                        if(cache.get(next) < min){
                            min = cache.get(next);
                            minKey = next;
                        }
                    }
                    cache.remove(minKey);
                }
                if(cacheSize > 0) cache.put(target, i);
                answer+=5;
            }
        }
        return answer;
    }
}