구현

프로그래머스 2018 KAKAO BLIND RECRUITMENT Level 2 문제 캐시를 Java를 이용해 풀어보았다.
비교적 쉬운 문제라 금방 풀기는 했지만 내 풀이보다 훨씬 직관적이고 간결한 코드들이 많았다. 아직 부족하다..

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/17680

큐를 이용해 LRU 구현

내가 짠 로직은 다음과 같다.

1. 주어진 cities 배열을 차례대로 순회하며 현재 도시가 큐에 있는지 확인한다.
2. 큐에 있으면 +1 해주고 해당 큐의 위치를 삭제하고, 맨 뒤에 다시 추가한다.
3. 큐에 없으면 +5 해주고 큐의 사이즈에 따라 꽉 차 있으면 맨 앞을 삭제하고 현재 도시를 맨 뒤에 추가하며, 큐의 자리가 남아있으면 그냥 추가해준다.

이렇게 전체 도시를 탐색하고 나면 답을 얻게 된다.

한 가지 예외 사항은, 캐시 사이즈가 0으로 주어졌을 경우에는 굳이 탐색을 진행하지 않고 바로 5 * 도시 개수 를 반환해주면 된다.

이를 코드로 표현하면 다음과 같다.

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

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

        if (cacheSize == 0) return 5 * cities.length;

        for (String city : cities) {
            boolean flag = false;
            Iterator<String> itr = q.iterator();
            while (itr.hasNext()) {
                String cmp = itr.next();
                if (city.equalsIgnoreCase(cmp)) { // 캐시에 있는 도시면
                    flag = true;
                    itr.remove(); // 삭제해주고
                    q.offer(cmp); // 우선 순위를 높이기 위해 맨 뒤로 보내주자
                    break;
                }
            }
            if (flag) { // 캐시에 들어있는 도시면
                answer += 1;
            }
            else { // 캐시에 없는 도시면
                if (q.size() == cacheSize) { // 캐시가 꽉 차있으면
                    q.poll(); // 가장 먼저 넣어준 도시 빼고
                    q.offer(city); // 새로 도시 넣어주자
                    answer += 5;
                } else if (q.size() < cacheSize) { // 캐시에 자리 남았으면
                    q.offer(city);
                    answer += 5;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int cacheSize = 3;
        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
        int res = solution(cacheSize, cities);
        System.out.println(res);
    }
}

아래 코드는 ArrayList의 indexOf 메소드를 사용해 내 풀이보다 훨씬 쉽게 구현한 코드다. 프로그래머스의 다른 사람들의 풀이를 살펴보다 정말 잘 작성한 코드라는 생각이 들어 첨부한다.

class Solution {
    public static int solution(int cacheSize, String[] cities) {
        int answer = 0, arrIdx = 0, citiesSize = cities.length;
        if(cacheSize==0) return cities.length*5;
        List<String> cache = new ArrayList<>();
        for(int i=0;i<citiesSize;i++){
            String city = cities[i].toLowerCase();
            int idx = cache.indexOf(city);
            if(idx>=0){ //Hit
                answer++;
                cache.remove(idx);
            } else { //Miss
                answer+=5;
                if(cache.size()>=cacheSize) cache.remove(0);
            }
            cache.add(city);
        }
        return answer;
    }
}