2018 - [1차] 캐시

https://programmers.co.kr/learn/courses/30/lessons/17680#

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

[ 문제풀이 ]

이번 문제는 페이지 교체 알고리즘 중 하나인 LRU(Least Recently Used)에 대한 사전 지식이 있다면 수월하게 해결할 수 있는 문제이다.

문제의 설명이 자세한 편이 아니라서 LRU에 대해서 잘 모른다면 문제를 이해하는데 조금 어려울 수도 있을 것 같다.

주의해야 할 점은 주어진 도시를 소문자, 대문자로 구분하지 않기 때문에 하나로 통일해 준다.

​또한, cacheSize가 0인 경우는 모든 도시가 cache hit가 될 수 없기 때문에 따로 처리해준다.

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
    	//cacheSize가 0인 경우 모든 도시는 cache hit가 될 수 없음
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        
        int answer = 0;
        ArrayList<String> list = new ArrayList<>();
        
        for (int i = 0; i < cities.length; ++i) {
        	//도시를 소문자로 변경
            cities[i] = cities[i].toLowerCase();
            
            //list에 도시가 있는지 판단
            int pos = list.indexOf(cities[i]);
            
            //도시가 없다면 +5점, 도시를 리스트 맨 뒤에 넣어줌
            if (pos == -1) {
                answer += 5;
                list.add(cities[i]);
                
                //리스트의 크기가 cacheSize보다 크다면 맨 앞의 도시를 제거
                if (list.size() > cacheSize) {
                    list.remove(0);
                }
            } 
            //도시가 있다면 +1점, 기존 도시를 제거하고 맨 뒤에 넣어줌
            else {
                answer += 1;
                list.remove(pos);
                list.add(cities[i]);
            }
        }
        
        return answer;
    }
}