[ 알고리즘 ] 코딩 - Programmers - 캐시.java

---

문제 링크

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

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

---

* 프로그래머스 - Level2 - (자바)캐시 - 리스트를 이용한 원소다루기

제한조건

제한 조건

입출력예시

* LRU ( Least Recently Used ) 페이지 교체 알고리즘을 사용

* LRU란 가장 최근에 사용되지 않은 페이지부터 교체하는 알고리즘

 

---

< 로직 >

* LRU 알고리즘을 리스트로 구현

* 새로 들어온 요소가 현재 리스트에 있는지 없는지 파악

* 있다면 해당 요소 리스트에서 제거 후 재입력 (가장 뒤로 보내야한다)

* 없다면 주어진 캐시 사이즈 확인

* 리스트가 캐시 사이즈와 같다면 가장 앞 원소 제거 후 현재 도시 입력

* 아래의 그림과 같은 로직

---

import java.util.ArrayList;
import java.util.List;
class Solution {
		int HIT = 1, NOHIT = 5;
	    public int solution(int cacheSize, String[] cities) {
	    	// 캐시길이가 0이라면 하나도 히트될 수 없음
	    	if(cacheSize == 0) return cities.length * NOHIT;
	    	List<String> list = new ArrayList<String>();
	    	
	    	int answer = 0;
	    	
	    	for(int i = 0; i < cities.length; i++) {
	    		// 현재 캐시 리스트에 현재 도시가 있는지 없는지 파악
	    		if(isHit(list, cities[i].toLowerCase(), cacheSize)) {
	    			answer += HIT; // 있으면 + 1
	    		} else {
	    			answer += NOHIT; // 없으면 + 5
	    		}
	    	}
	    	
	        return answer;
	    }
	    
		private boolean isHit(List<String> list, String city, int cacheSize) {
			boolean flag = false; // HIT / NOHIT 구분 flag
			if(list.contains(city)) { // 리스트에 있으면
				list.remove(city); // 현재 도시 일단 제거
				flag = true; // HIT!
			} else { // NOHIT!
				if(list.size() == cacheSize) { // 리스트와 캐시 사이즈가 같은 경우
					list.remove(0); // 가장 앞 원소 제거
				}
				flag = false;
			}
			list.add(city); // 맞았든 맞지 않았든 현재 도시 가장 마지막 배치
			
			return flag;
		}
	}