[프로그래머스][LEVEL2] 캐시 - JAVA

[문제]

• 2018 KAKAO BLIND RECRUITMENT 출제 

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

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

 

[풀이]

<사전 지식>

1. LRU 캐시 알고리즘의 동작 방법을 알고 있어야 한다. 

https://programmer-chocho.tistory.com/14

LRU(Least Recently Used) 캐시 알고리즘

 

2. 캐시 용어

• Cache Hit: CPU가 참조하고자 하는 메모리가 캐시안에 존재하는 경우
• Cache Miss: CPU가 참조하고자 하는 메모리가 캐시안에 없는 경우

 

[코드]

- Queue를 이용했다. 

package com.algorithm.kakaoTest.three;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 캐시
 * 소요시간: 21분 36초
 */
public class Test01 {
    public static void main(String[] args) {
        int cacheSize = 2;
        String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};

        int answer = solution(cacheSize, cities);
        System.out.println(answer);
    }

    public static int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> cache = new LinkedList<>();

        // 캐시 크기가 0이면 항상 캐시 miss이므로 모든 수행시간이 5초임
        if (cacheSize == 0) {
            return cities.length * 5;
        }

        for (int i = 0; i < cities.length; i++) {
            String city = cities[i].toLowerCase();

            if (!cache.contains(city)) { // 캐시 miss
                answer = answer + 5;
                if (cache.size() == cacheSize) {
                    cache.poll();
                }
            } else { // 캐시 hit
                answer = answer + 1;
                cache.remove(city);
            }
            cache.add(city);
        }
        return answer;
    }
}