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

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

프로그래머스

Level 2. [1차] 캐시

2018 KAKAO BLIND RECRUITMENT

 

 

접근 방식
큐를 사용한다.
1. 초반(캐시 공간이 남을 때)에는 queue에 도시를 추가한다.
   -> 이때 캐시에 이미 존재하는 도시를 추가할 차례라면, 해당 도시는 삭제하고 queue의 마지막에 새로 추가한다.
2. 캐시 공간이 남지 않았을 때에는  queue에 존재하는지 안 하는지 확인한다.
   -> 존재한다면, hit이며 queue에서 해당 도시를 삭제하고 queue의 마지막에 새로 추가한다.
   -> 존재하지 않는다면, miss이며 queue의 맨 처음 도시를 삭제하고, 맨 마지막에 새로 도시를 추가한다.

 

 

처음 코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
     
     if(cacheSize==0)
    	 return 5*cities.length;
     
     Queue<String> queue = new LinkedList<>();
     
     for(int i=0; i<cities.length; i++) {
    	 
    	 //초반 (캐시 공간이 남음)
    	if(queue.size()<cacheSize) { 
    		// 존재하면 그냥 넘어간다 -> hit
    		if(queue.contains(city)) {
            //// 수정한 부분 //// 
                answer++;
    		}
    		//안 존재하면 miss, 추가해준다 
    		else {
    			queue.add(city);
    			answer+=5;
    		}
    	}
    	
    	//확인 필요
    	else {
    		//갖고 있는 애면 hit고, queue에 순서 바꿔줌
    		if(queue.contains(city)) {
    			queue.remove(city);
    			queue.add(city);
    			answer++;
    		}
    		
    		//안 갖고 있는 애면 miss
    		else {
    			queue.remove();
    			queue.add(city);
    			answer+=5;
    		}
    	}
     }
     return answer;
    }
}

 

처음 코드는, 모든 도시를 소문자와 대문자를 구분하여 오답이었다. 해당 문제는 반복문을 시작하기 전, 소문자로 모두 변경하여 해결하였다.

두 번째 문제는, 수정한 부분이라고 표시된 부분이 잘못되었었는데 캐시의 공간이 남았고, 이미 존재하는 도시를 확인할 때가 문제였다. 이미 존재하고 캐시의 공간이 남았다면 그냥 넘어가는 방법으로 문제를 풀었었는데, 해당 경우는 큐의 순서를 바꾸어주어야 한다는 사실을 간과하였다. 해당 도시를 삭제하고, 다시 큐에 추가하는 방법으로 해결할 수 있었다. 

 

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
     int answer = 0;
     
     if(cacheSize==0)
    	 return 5*cities.length;
     
     Queue<String> queue = new LinkedList<>();
     
     for(int i=0; i<cities.length; i++) {
    	 String city = cities[i].toLowerCase();
    	 
    	 //초반 (캐시 공간이 남음)
    	if(queue.size()<cacheSize) { 
    		// 존재하면 그냥 넘어간다 -> hit
    		if(queue.contains(city)) {
    			queue.remove(city);
    			queue.add(city);
                answer++;
    		}
    		//안 존재하면 miss, 추가해준다 
    		else {
    			queue.add(city);
    			answer+=5;
    		}
    	}
    	
    	//확인 필요
    	else {
    		//갖고 있는 애면 hit고, queue에 순서 바꿔줌
    		if(queue.contains(city)) {
    			queue.remove(city);
    			queue.add(city);
    			answer++;
    		}
    		
    		//안 갖고 있는 애면 miss
    		else {
    			queue.remove();
    			queue.add(city);
    			answer+=5;
    		}
    	}
     }
     return answer;
    }
}

 

 

고찰

해당 문제는 LRU에 대한 정확한 이해와 응용이 필요한 문제이다. LRU에 대한 이론이 정확하지 않다면 제대로 풀 수 없다. 

또, queue를 사용하면 단순하게 풀 수 있다.

 

여러 가지 테스트 케이스를 계속해서 확인해보면서 정답을 맞출 수 있는 문제였다.

많은 테스트 케이스가 있는 경우에는 문제를 정확하게 이해할 수 있는데, 그렇지 못하다면 쉽지 않을 것 같았다.

많은 경우의 수를 스스로도 생각해볼 수 있어야 할 것 같다. 

또, 학기 중에 LRU 알고리즘을 작성해본 적 있는데, 그때보다 훨씬 수월하게 풀 수 있었기 때문에 그래도 조금은 성장한 것(...) 같다고 느꼈다.

많이 풀어보고 해결할 수 있는 능력을 길러야겠다.