프로그래머스 캐시 Java - 2018 카카오 블라인드 채용

29 March 2020 - less than 1 min read time
Tags: 알고리즘 프로그래머스

문제

문자열로 구성된 도시 리스트를 캐시 사이즈와 LRU캐시를 기반으로 적용했을 때 총 실행시간을 구하라

도시는 소문자/대문자가 섞여있고 공백/특수문자는 없다. LRU 캐시는 가장 최근에 교체되지 않는 값을 바꾸는 기법중 하나로 가장 오랜 기간 사용하지 않은 것을 제거하면 된다.

접근

주어진 문자열의 값을 캐시할 자료구조를 선언
캐시를 위한 자료구조에 값이 존재하면 hit 실패하면 miss 에 따라 실행시간 더하기
hit 일 경우 캐시 기법에 따라 참조 값 이동
miss 일 경우 캐시 사이즈가 부족한 경우 가장 오래된 값 제거하고 새로운 값을 저장

풀이

1번

int answer = 0;

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

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

    if(list.contains(temp)) { //hit
        answer += 1;

        int idx = list.indexOf(temp);
        list.remove(idx);
        list.add(temp);
    } else { //miss
        answer += 5;
        if(cacheSize > 0) {
            if(list.size() >= cacheSize)
                list.remove(0);
            list.add(temp);                    
        }
    }
}

return answer;