2018 카카오 블라인드 코딩테스트 - [1차] 캐시 (feat. Java)

문제 정보는 아래 링크를 확인해주세요!

[캐시]

 

프로그래머스

 

문제 접근 방법

• LRU(최근에 참조되지 않은 순서부터 제거하는 방법) 캐시를 구현하는 방법으로
• 캐시를 저장할 리스트를 하나 만들어준다.
• 도시 배열을 돌면서
• 도시 이름이 캐시에 포함되어 있다면,
• 해당 도시를 참조했으므로 리스트의 맨 뒤로 보내고 실행시간 +1 증가
• 도시 이름이 캐시에 포함되어있지 않다면,
• 캐시가 꽉차있는지 확인하고 꽉차있다면,
• 가장 오래 참조되지 않았던 캐시가 리스트의 맨앞에 존재하므로 그것을 지워주고 새로운 도시를 캐시에 추가
• 새로운 캐시를 추가했으므로 실행시간 +5를 해준다.

[소스 코드]

package algorithm.programmers;

import java.util.*;

/*
 * 2018 KAKAO BLIND RECRUITMENT
 * [1차] 캐시
 * */
public class Pro17680 {

    public int solution(int cacheSize, String[] cities) {
        ArrayList<String> lru = new ArrayList<>();

        int answer = 0;

        if (cacheSize == 0) {//캐시 사이즈가 0이면, 배열 길이*5로 반환
            answer = cities.length*5;
            return answer;
        }

        for (String city : cities) {

            String temp = city.toUpperCase();//도시 이름을 대문자로 통일

            if (lru.contains(temp)) {//LRU 캐시에 포함되어 있다면,

                lru.remove(temp);//도시 이름을 참조했으므로, 다시 맨뒤로 보낸다.
                lru.add(temp);
                answer++;//시간을 1증가

            } else {

                //LRU 캐시 사이즈가 꽉차있다면, 제일 오래된 캐시를 제거
                if (lru.size() == cacheSize) lru.remove(0);

                lru.add(temp);//캐시에 새로운 도시 이름을 추가

                answer+=5;//새로운 캐시를 참조했으므로, +5를 해준다.
            }
        }

        return answer;
    }
}