[1차] 캐시

<풀기 전 생각>

중복을 허용하지 않는 다는 점에서 HashSet 자료구조를 사용하면 어떨까 생각이 들어 해당 자료구조를 사용하여

Set 을 사용
	if 기존에 없는 요소 접근
		if Set의 사이즈가 지정 크기를 벗어나면
    			맨앞의 요소를 삭제 Set에 해당 요소 추가
        	ans+5
	else 기존에 있는 요소 접근
		Set에 추가 ans+1

다음과 같은 방식으로 문제의 알고리즘을 생각했다. 

 

<결과 코드 (실패)>

import java.util.*;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    private void deleteFirstFail(HashSet<String> cash){
        Iterator<String> it = cash.iterator();
        cash.remove(it.next());
    }
    public int solutionFail(int cacheSize, String[] cities) {
        int answer = 0;
        HashSet<String> cash = new HashSet<String>();
        for (String citie:cities) {
            String city = citie.toUpperCase();
            // 캐쉬에 없는 요소 접근
            if(!cash.contains(city)){
                if(cash.size()!=0&&cash.size()>=cacheSize)
                    deleteFirstFail(cash);
                answer+=5;
            }
            // 캐쉬에 있는 요소 접근
            else {
                cash.remove(city);
                answer++;
            }
            // 공통되는 부분이므로 밖으로 빼냄
            cash.add(city);
        }
        return answer;
    }
}

<중간 문제점>

Set은 순서를 보장해주지 않는다는 것을 순서를 보장해주는 것으로 착각한 상태 였기 때문에 해당 풀이는 완전히 틀린 풀이가 되었다. 그래서 위에서 고안한 Set을 가장 오래 사용되지 않던 도시를 캐쉬에서 제거한다는 문제의 설명이 떠올라 자료구조 Queue을 Set과 대신 사용하는 방식으로 다시 접근 하게 되었다.

 

<최종 코드>

import java.util.*;

class Solution {
    // 시간 복잡도 O(n^2) LinkedList.contains의 시간 복잡도는 O(n)이기 때문
    // 공간 복잡도 O(1)
    public int solution(int cacheSize, String[] cities) {
        // 캐쉬 사이즈 0일 때의 예외 처리
        if(cacheSize==0)
            return cities.length*5;

        int answer = 0;
        Queue<String> cash = new LinkedList<String>();
        for (String citie:cities) {
            String city = citie.toUpperCase();
            // 캐쉬에 없는 요소 접근
            if(!cash.contains(city)){
                if(cash.size()!=0&&cash.size()>=cacheSize)
                    cash.remove();
                answer+=5;
            }
            // 캐쉬에 있는 요소 접근
            else
                answer++;
			// 공통적인 부분이므로 바깥으로 빼냄
            cash.offer(city);
        }
        return answer;
    }
}

 <메모>

다른 사람들의 풀이를 살펴본 결과 해당 방식으로 애초에 해당 문제에 최적화된 자료구조를 만들어서 풀이 한 걸 볼 수 있었는데 참고 해둘 필요가 있어 보인다.

class LRU<K, V> extends LinkedHashMap<K, V>