[프로그래머스] 캐시 (Java)

프로그래머스

Least Recently Used (LRU) 캐시 알고리즘을 구현하는 문제로 특이사항은 없었다.

 

- cacheSize가 0인 경우 전부 miss이므로 (5 * cities 배열 길이) 반환

- cache로 사용할 LinkedList 선언

- cities를 탐색하며

1) 도시 이름 city 소문자로 변경

2) cache를 탐색하며 hit인 경우 현재 위치의 city 제거 후 0번 위치에 city삽입, isHit true로 변경 (시간: 1)

3) miss인 경우(!hit) cache가 찼는지를 확인하여 마지막(가장 안 쓰인) cache제거 후 city 삽입 (시간: 5)

 

Note

- 자바 컬렉션 LinkedList가 애초에 Doubly Linked List로 구현되어있다는 걸 이번에 알게되었다.

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        if(cacheSize == 0){
            return cities.length * 5;
        }
        
        List<String> cache = new LinkedList<String>();
        
        for(String city : cities){
            city = city.toLowerCase();
            Boolean isHit = false;
            for(int i = 0; i < cache.size(); i++){
                if(cache.get(i).equals(city)){
                    cache.remove(i);
                    cache.add(0, city);
                    isHit = true;
                    answer += 1;
                    break;
                }
            }
            if(!isHit){
                if(cache.size() == cacheSize){
                    cache.remove(cacheSize - 1);
                }
                cache.add(0, city);
                answer += 5;
            }
        }
        
        return answer;
    }
}