[프로그래머스 / 2018 KAKAO BLIND RECRUITMENT / 자바(JAVA)] [1차] 캐시

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

 

▼ ▼ ▼

정답 풀이로 바로 가기

▲ ▲ ▲

 

내 풀이 (오답)

로직

1. ArrayList를 활용해 이를 구현해보자.
2. cities 배열을 모두 도는 확장 for문을 사용한다.
3. 대소문자의 구분이 없다고 했으므로, str에 toLowerCase()를 적용한다.
4. str과 cache에 대한 조건문에 따라 코드를 수행해준다.
   • 만약 cache가 str를 포함하고 있다면,
     • cache hit이므로 answer++을 해준다.
     • str을 cache에서 remove 해주고, 가장 나중의 index에 다시 추가해준다.
   • 위 조건에는 해당하지 않으나, cache.size()가 cacheSize를 넘어선다면
     • cache miss에 해당하므로 answer+=5를 해준다.
     • 0번째 인덱스의 자료를 지워준다. (가장 오래 전 사용된 것이므로)
     • str을 add 해준다.
   • 위 두 조건 모두에 해당하지 않으면
     • cache miss에 해당하므로 answer+=5를 해주고,
     • str을 add 해준다.

코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {

        int answer = 0;
        List<String> cache = new ArrayList<>();

        for(String str : cities) {
            str = str.toLowerCase();

            if(cache.contains(str)) { // cache hit
                answer++;
                cache.remove(str);
                cache.add(str);
            } else if(cache.size()>cacheSize) { // cache miss
                answer += 5;
                cache.remove(0);
                cache.add(str);
            } else { // cache miss
                answer += 5;
                cache.add(str);
            }    
        }

        return answer;
    }
}

채점 결과

정확성  테스트
테스트 1 〉    통과 (0.06ms, 74.7MB)
테스트 2 〉    통과 (0.06ms, 76.1MB)
테스트 3 〉    통과 (0.08ms, 78.6MB)
테스트 4 〉    통과 (0.05ms, 74.7MB)
테스트 5 〉    통과 (0.04ms, 73.9MB)
테스트 6 〉    통과 (0.04ms, 77.2MB)
테스트 7 〉    실패 (0.12ms, 77.1MB)
테스트 8 〉    통과 (0.10ms, 75.4MB)
테스트 9 〉    통과 (0.06ms, 73.3MB)
테스트 10 〉    통과 (0.23ms, 74.3MB)
테스트 11 〉    실패 (36.74ms, 120MB)
테스트 12 〉    실패 (0.20ms, 81.1MB)
테스트 13 〉    실패 (0.64ms, 78.8MB)
테스트 14 〉    실패 (1.23ms, 71.9MB)
테스트 15 〉    실패 (1.17ms, 77.1MB)
테스트 16 〉    실패 (1.37ms, 85.2MB)
테스트 17 〉    실패 (1.56ms, 87.3MB)
테스트 18 〉    실패 (1.61ms, 84.9MB)
테스트 19 〉    실패 (1.60ms, 74.7MB)
테스트 20 〉    실패 (2.01ms, 79.9MB)

채점 결과
정확성: 45.0
합계: 45.0 / 100.0

 

 

내 풀이 (정답)

로직

cache.size()가 cacheSize와 같을 때
가장 처음에 위치한 자료를 없애고 str을 추가해야한다.

코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {

        int answer = 0;
        if(cacheSize==0) return cities.length*5;

        List<String> cache = new ArrayList<>();

        for(String str : cities) {
            str = str.toLowerCase();

            if(cache.remove(str)) { // cache hit
                answer++;
                cache.add(str);
            } else if(cache.size()==cacheSize) { // cache miss
                answer += 5;
                cache.remove(0);
                cache.add(str);
            } else { // cache miss
                answer += 5;
                cache.add(str);
            }    
        }

        return answer;
    }
}

 

채점 결과

정확성  테스트
테스트 1 〉    통과 (0.05ms, 78.7MB)
테스트 2 〉    통과 (0.06ms, 88.4MB)
테스트 3 〉    통과 (0.05ms, 76.6MB)
테스트 4 〉    통과 (0.08ms, 68MB)
테스트 5 〉    통과 (0.06ms, 66.3MB)
테스트 6 〉    통과 (0.02ms, 77.1MB)
테스트 7 〉    통과 (0.02ms, 77.9MB)
테스트 8 〉    통과 (0.07ms, 83.2MB)
테스트 9 〉    통과 (0.06ms, 74.6MB)
테스트 10 〉    통과 (0.32ms, 76.2MB)
테스트 11 〉    통과 (36.79ms, 123MB)
테스트 12 〉    통과 (0.26ms, 74MB)
테스트 13 〉    통과 (0.70ms, 78MB)
테스트 14 〉    통과 (0.82ms, 91.2MB)
테스트 15 〉    통과 (1.38ms, 75.9MB)
테스트 16 〉    통과 (1.20ms, 73.9MB)
테스트 17 〉    통과 (0.02ms, 85.6MB)
테스트 18 〉    통과 (1.64ms, 73.7MB)
테스트 19 〉    통과 (1.68ms, 76.9MB)
테스트 20 〉    통과 (1.87ms, 77.2MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

 

좋은 풀이

wonho , 조현지 , 최광순 님의 풀이

import java.util.LinkedHashMap;
import java.util.Map;

class Solution {
  public int solution(int cacheSize, String[] cities) {
      int answer = 0;
        LRU<String, String> clsTemp = LRU.newInstance(cacheSize); 
        for (int i = 0; i < cities.length; i++) {
            String sTemp = cities[i].toUpperCase();
            if(clsTemp.containsKey(sTemp)) {
                answer++;
            }else {
                answer +=5;
            }
            clsTemp.put(sTemp, sTemp);
        }

        return answer;
    }
}

class LRU<K, V> extends LinkedHashMap<K, V> {
    private int size;

    private LRU(int size) {
        super(size, 0.75f, true);
        this.size = size;
    }
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }
    public static <K,V> LRU<K,V> newInstance(int size) {
        return new LRU<K,V>(size);
    }
}

 

배운 점

1. LRU (Least Recently Used) 캐시 알고리즘
   • https://eunzzzzz1.tistory.com/25

   • [페이지 교체 알고리즘] LRU (Least Recently Used) 캐시 알고리즘

2.  LinkedHashMap
   • https://eunzzzzz1.tistory.com/24  

   • [JAVA] LinkedHashMap의 사용