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

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

프로그래머스

문제

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오

 

입력형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 <= cacheSize <= 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000 개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력형식

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU (Least Recently Used)를 사용한다.
• cache hit 일 경우 실행시간은 1 이다.
• cache miss 일 경우 실행시간은 5 이다.

입출력 예제

풀이

 

Queue를 사용할려고 하였지만, Stack 처럼 Search 메서드가 없었어 cache hit 일 경우를 찾기 힘들거라 판단하여 ArrayList를 사용 하였습니다.

ArrayList<String> list = new ArrayList<>();

 

cacheSize가 '0' 일 경우에는 무조건 cache miss 이기에 도시이름 배열 크기 * 5를 하였습니다.

if (cacheSize == 0) {	
    return cities.length * 5;
}

 

대소문자 구분을 하지 않기에 도시이름 배열 값을 항상 소문자로 만들고, list에 lowtemp의 값이 있는지 확인한다.

indexOf()는 특정문자나 문자열이 앞에서부터 처음 발견되는 인덱스를 반환하며, 만약에 찾지 못했을 경우 "-1"을 반환하고, 찾으면 '0' 부터 값이 시작된다.

String lowtemp = cities[i].toLowerCase();		
int j = list.indexOf(lowtemp);

 

indexOf()의 값이 '-1'을 반환하면 list의 값에 값은 값이 없다는 것으로 list.size()가 cacheSize와 다를 경우 list에 값을 넣어주고 아니면 가장 오랫동안 들어 와 있던 값 제거(LRU) 해주고 새로운 값을 추가 해주면 된다.

if (j == -1) {     //같은 값 없을 때

    if(list.size() != cacheSize) {
    
        list.add(lowtemp);
        answer += 5;
        
    } else {
    
        list.remove(0);
        list.add(lowtemp);
        answer += 5;
        
    }
} 

 

list에 값은 값이 있을경우 그 값을 제거 해주고 최근에 들어 온 값으로 add 해준다.

else {    //같은 값 있을 때
			
    list.remove(j);
    list.add(lowtemp);
    answer += 1;
			
}

 

전체 코드

Queue, Stack, ArrayLIst에 대해서 다시 한번 생각해 볼 수 있는 문제 였습니다.

import java.util.*;
class Solution {
  public int solution(int cacheSize, String[] cities) {
      
    int answer = 0;      	
    ArrayList<String> list = new ArrayList<>();
		
    if (cacheSize == 0) {	
        return cities.length * 5;
    }
		
    for (int i = 0; i < cities.length; i++) {
    
        String lowtemp = cities[i].toLowerCase();			
        int j = list.indexOf(lowtemp);
        
        if (j == -1) {                        //같은 값 없을 때
            if(list.size() != cacheSize) {
                list.add(lowtemp);
                answer += 5;
            } else {
                list.remove(0);
                list.add(lowtemp);
                answer += 5;
            }
        } else {                                //같은 값 있을 때		
            list.remove(j);
            list.add(lowtemp);
            answer += 1;			
        }
    }
    
    return answer;
  }
}