[프로그래머스-lv2 2018 KAKAO BLIND RECRUITMENT] 캐시 -Java

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

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

import java.util.ArrayList;
import java.util.List;
class Solution {
	    public int solution(int cacheSize, String[] cities) {
	        int answer = 0;
	        if(cacheSize==0) return cities.length*5;
	        
	        List <String> disk = new ArrayList<>();
	        for(int i=0; i<cities.length; i++) {
	        	String city=cities[i].toUpperCase(); //대소문자 구분 x -> 다 대문자로
	        	
	        	if(!disk.contains(city)) { //디스크에 없고 
	        		answer+=5; // answer+5
	        		if(disk.size()==cacheSize) disk.remove(0); // 꽉차있으면 0번 인덱스 삭제
	        	}
	        	else{ //디스크에 존재한다면 
	        		answer+=1; //원래들어있떤 순위 삭제  answer+1
	        		for(int idx=0; idx<disk.size(); idx++) { 
	        			if(disk.get(idx).equals(city)) disk.remove(idx);
	        		}
	        	}
	        	
	        	disk.add(city); //가장 최근으로 삽입
	        }
	        return answer;
	    }
	}

소요시간 : 20분

 

LRU에 대한 개념만 있다면 빠르게 풀 수 있는 문제입니다.

 

로직을 살펴보면 

 

우선 대소문자 구분이 없기 때문에 cities배열을 돌면서 대문자로 바꿔줍니다.

 

LRU로 알고리즘을 사용할 때 경우의 수는 3가지입니다.

 

1. 현재 disk에 없고 disk가 꽉차있다. (miss)

- 리스트에서 0번인덱스를 삭제하고 city를 리스트에 삽입

2. 현재 disk에 없고 disk에 자리가 있다. (miss)

- city를 리스트에 삽입

3. 현재 disk에 있다. (catch)

- 인덱스를 찾아서 삭제하고 city를 리스트에 삽입

 

끝~