[Programmers / Level 2] 17680. 2018 KAKAO BLIND RECRUITMENT [1차] 캐시 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17680
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/[1차] 캐시

입출력 조건

입출력 예시

문제 이해

• 캐시 크기에 따라 실행 시간이 달라지는 프로그램을 교차 알고리즘으로 만드는 문제

알고리즘

풀이 시간 : 27분

• LRU 캐시
  • 캐시 히트(캐시에 있음) -> 기존 데이터 삭제 후 최신 위치로 갱신 -> 실행 시간 +1
  • 캐시 미스(캐시에 없음)
    • 캐시가 가득 차면 가장 오래된 데이터 삭제
    • 새 데이터를 추가 -> 실행 시간 +5

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) return cities.length * 5;

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

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

            if (cache.contains(city)) {
                cache.remove(city);
                answer += 1;
            } else {
                if (cache.size() == cacheSize) {
                    Iterator<String> it = cache.iterator();
                    it.next();
                    it.remove();
                }
                answer += 5;
            }
            cache.add(city);
        }

        return answer;
    }
}

결과