프로그래머스 - [1차] 캐시

[1차] 캐시 :https://programmers.co.kr/learn/courses/30/lessons/17680

Problems

---

Solves

캐시 알고리즘을 LRU(Least Recently Used)알고리즘을 사용한다는 것에 힌트를 얻어 LinkedList< String >로 캐시를 구현하고 cities를 돌면서 해당 도시의 캐시 포함여부를 확인한다.
캐시에 도시가 포함되어있을때 해당 도시를 캐시에서 삭제하고 LinkedList 맨 뒤에 도시를 다시 저장해주고 answer+=1
(캐시 앞쪽일수록 사용한지 오래된 도시, 캐시 뒤쪽일수록 최근 사용한 도시)
캐시에 도시가 포함되어있지 않을때 캐시가 cacheSize만큼 저장되어있다면 맨 앞쪽의 도시를 제거하고 맨 뒤에 해당 도시를 저장한다. 그렇지 않다면 맨 뒤에 해당 도시를 저장만 하고 answer+=5

모든 도시를 탐색했다면 answer 반환.

---

Code

import java.util.LinkedList;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        LinkedList<String> cache = new LinkedList<>();
        
        int answer = 0;
        
        if(cacheSize>0){
            for(String c : cities){
            //대소문자 구분 x
            c = c.toLowerCase();
            //캐시에 도시가 저장되어있다면
            if(cache.contains(c)){
                answer += 1;
                //캐시의 기존 도시 제거
                cache.remove(c);
                //맨 뒤에 도시 저장
                cache.add(c);
            }
            //저장되어있지않다면
            else{
                answer += 5;
                //캐시가 cacheSize만큼 도시가 저장되어있다면
                if(cache.size()==cacheSize){
                	//사용한지 가장 오래된 도시 제거
                    cache.removeFirst();
                }
                //캐시 맨 뒤에 도시 저장
                cache.add(c);
            }
            }   
        }
        //cacheSize가 0이라면 answer = 도시의 총 갯수 * 5
        else{
            answer = 5*cities.length;
        }
        
        return answer;
    }
}

---

Result