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

🔗 문제 링크

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

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

 

📝 풀이 과정

가장 최근 참조하지 않은 것을 교체하는 LRU 알고리즘을 구현해보는 문제이다.
입력순으로 정렬도 가능하면서 빠르게 저장된 값이 있는지도 판별해야하기 때문에 LinkedHashSet을 사용하기로 했다.

 

 

city = city.toLowerCase();
ans += cache.contains(city) ? 1 : 5;

먼저, 대소문자 구분이 없다고 주어졌기 때문에 str.toLoverCase()를 통해 문자열을 소문자로 변경시켜주었다. 이후, 변경된 문자열이 cache에 존재한다면 답에 1초를 더해주고 없다면 5초를 더해주었다.

 

 

cache.remove(city);
cache.add(city);

cache에 재정렬하기 위해 먼저 remove를 통해 기존에 있던 값을 삭제해주고 add를 통해 다시 넣어주며 입력순서를 갱신해 주었다.

 

 

if (cache.size() > cacheSize)
  cache.remove(cache.iterator().next());

만약 위에서 제거되지 않고 새롭게 값이 추가만 되었다면 cache의 크기는 증가하고 cache의 크기가 cacheSize보다 커지게 되면 cache에서 제일 오래전에 추가된 값을 제거해주면 된다.

 

💻 코드

import java.util.LinkedHashSet;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int ans = 0;
        LinkedHashSet<String> cache = new LinkedHashSet<>();

        for (String city : cities) {
            city = city.toLowerCase();
            ans += cache.contains(city) ? 1 : 5;

            cache.remove(city);
            cache.add(city);

            if (cache.size() > cacheSize)
                cache.remove(cache.iterator().next());
        }

        return ans;
    }
}