프로그래머스 / 캐시 (JAVA)

문제 설명

캐시 크기에 따른 실행시간 측정 프로그램을 작성하는 것이다.

 

조건 1 : 캐시 교체 알고리즘 LRU(Least Recently Used)를 사용한다.

조건 2 : cache hit일 경우 실행시간은 1이다.

조건 3 : cache miss일 경우 실행 시간은 5이다.

조건 4 : 영문자로만 구성되어 있으며, 대소문자 구분을 하지 않는다.

 

LRU 알고리즘 : 가장 오랫동안 사용되지 않은 데이터를 삭제하고 새로 추가

LFU 알고리즘 : 가장 적은 참조 횟수를 가진 데이터를 삭제하고 새로 추가

 

내가 생각한 해결 방법

가장 오랫동안 사용하지 않은 데이터를 삭제하는 것이기 때문에 큐를 사용하면 될것이라 생각하였다. 

큐는 FIFO방식으로 그전에 cache가 hit 된다면 앞에 있는 데이터를 삭제하고, miss 된다면 cacheSize를 고려하여 추가하면 된다. 

 

입출력 예제

캐시크기(cacheSize)	도시이름(cities)	실행시간
3	[Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA]	50
3	[Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul]	21
2	[Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome]	60
5	[Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome]	52
2	[Jeju, Pangyo, NewYork, newyork]	16
0	[Jeju, Pangyo, Seoul, NewYork, LA]	25

 

1. 대소문자를 고려하지 않기 때문에 편의를 위해 toUpperCase 함수를 통해 전부 대문자로 바꾸었다. 

배열의 첫번째를 임의로 큐에 먼저 넣어주고 answer의 값도 cache miss를 의미하는 5로 초기 값을 설정하였다. 

2. 그리고 cities 배열 요소가 cache 큐 안에 들어있는지 체크를한다. 

3. 포함 되어 있다면 큐안의 요소를 삭제하고 새로 큐에 추가하였다. 그 후 answer 값 증가

4. 포함되어 있지 않을때

-4.1 만약 큐의 크기가 cacheSize보다 크다면 큐의 맨 앞 요소를 삭제하였다.

-4.2 그 후 새로운 데이터를 삽입하고 answer의 값을 5증가 하였다.

 

 

☆지문에서 cacheSize가 0이상 30이하라고 나와있다.

cacheSize가 0일때는 전부 miss가 되기 때문에 큐의 값 * 5를 리턴 처리 하였다. 

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int solution(int cacheSize, String[] cities) {
		int answer = 5;
		Queue<String> cache = new LinkedList<>();
		for(int i=0; i<cities.length;i++) {
			cities[i] = cities[i].toUpperCase();
		}
		cache.offer(cities[0]);

		for(int i=1; i<cities.length;i ++) {
			if(cache.contains(cities[i])) {
				cache.remove(cities[i]);
				cache.offer(cities[i]);
				answer++;
			}else {
				
				if(cache.size()>=cacheSize) {
					cache.remove();
				}
				cache.offer(cities[i]);
				answer += 5;
			}
		}
        if(cacheSize ==0) return cities.length*5;

		return answer;
    }
}

지문은 굉~~~~~~~~~장히 길지만 나름 쉽게 풀었던 거 같다 ㅎ

 

 

만약에 LFU알고리즘으로 구현하라고 했으면 각 요소가 언급될 때 마다 따로 횟수를 저장할 공간을 만들어야할 거 같다.

음 횟수를 저장할 배열을 만들어야하나??