[프로그래머스] 캐시

 

https://school.programmers.co.kr/learn/courses/30/lessons/17680

 

프로그래머스

 

코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > [1차] 캐시

후기

네 시간 동안 이 문제를 붙잡고 있었는데 결국은 ArrayList<String>으로 간단하게 해결했다.

문제를 어렵게 푸는 경향이 있는 것 같다.

왜인지 1차인데 어렵다 했다.

LRU를 이중 연결 리스트로 구현한다는 접근 방식에서 삽질을 했던 것 같다.

ArrayList의 remove의 쓰임을 새롭게 알게 됐다.

 

처음에는 인덱스로만 접근 가능한 줄 알고

arrayList.remove(arrayList.indexOf(city));

이렇게 작성했었는데 자바가 최적화해주었다.

arrayList.remove(city); // remove는 city가 있는 인덱스를 찾아서 지워준다.

코드

import java.util.ArrayList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        ArrayList<String> arrayList = new ArrayList<>();
        
        if(cacheSize == 0) return cities.length * 5;


        for (String city : cities) {
            city = city.toUpperCase();
            
            if(arrayList.contains(city)) {
                arrayList.remove(city);
                arrayList.add(city);
                answer += 1;
            } else {
                if(arrayList.size() == cacheSize) {
                    arrayList.remove(0);
                }
                arrayList.add(city);
                answer += 5;
            }
        }

        return answer;
    }
}

 

 

삽질 기록

문제에서 캐시 교체 알고리즘은 LRU를 사용한다.

 

Least Recently Used Algorithm

LRU 알고리즘이란 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법이다.

 

 

Test case 2를기준으로 생각해보았다.

//  <Test case 2>
int cacheSize = 3;
String[] cities = {"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};

head(Recent) - [] - [] - [] - tail(Old)
head(Recent) - [] - [] - [Jeju] - tail(Old) : Miss
head(Recent) - [] - [Pangyo] - [Jeju] - tail(Old) : Miss
head(Recent) - [Seoul] - [Pangyo] - [Jeju] - tail(Old) : Miss
head(Recent) - [Jeju] - [Seoul] - [Pangyo] - tail(Old) : Hit
head(Recent) - [Pangyo] - [Jeju] - [Seoul] - tail(Old) : Hit
head(Recent) - [Seoul] - [Pangyo] - [Jeju] - tail(Old) : Hit
head(Recent) - [Jeju] - [Seoul] - [Pangyo] - tail(Old) : Hit
head(Recent) - [Pangyo] - [Jeju] - [Seoul] - tail(Old) : Hit
head(Recent) - [Seoul] - [Pangyo] - [Jeju] - tail(Old) : Hit

// 따라서, Miss(5) * 3 + Hit(6) * 1 = 21

 

LRU 구현

이중 연결 리스트(Doubly Linked List)를 사용했다.

class Node<E> {
    E data;
    Node<E> prev; // 이전 Node를 가리키는 reference 변수
    Node<E> next; // 다음 Node를 가리키는 reference 변수

    Node(E data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

 

처음에는 아래 코드처럼 DoublyLinkedList<E>로 구현하는 방법을 시도해보았지만 모든 메서드를 만들어야 해서 결국 ArrayList<Node<String>> 를 사용했다.

// Doubly Linked List
public class DoublyLinkedList<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

 

head, tail 초기화

        // head, tail 초기화
        Node<String> head = new Node<>("");
        Node<String> tail = new Node<>("");

        tail.next = head;
        head.prev = tail;
        
        // head(Recent) - [] - [] - [] - tail(Old)
        arrayList.add(tail); // tail(Old)

 

cities에 있는 값들을 ArrayList에 넣을 때 다음과 같이 들어갈 것이다.

        // cities[0] : Jeju
        // head(Recent) - [] - [] - [Jeju] - tail(Old) : Miss
        // cities[0] : Jeju
        // 가장 첫 번째이므로 캐시에 있는지 확인 안 해도 됨.
        Node<String> newNodeTest = new Node<>("Jeju"); //  newNode : Jeju
        newNodeTest.prev = tail;
        newNodeTest.next = head;
        arrayList.add(newNodeTest); // arrayList : Jeju - tail(Old)

        // cities[1] : Pangyo
        // head(Recent) - [] - [Pangyo] - [Jeju] - tail(Old) : Miss
        // 기존에 arrayList에 city가 있는지 확인
        Node<String> Pangyo = new Node<>("Pangyo"); //  newNode : Pangyo

        // 있으면
        Pangyo.prev = arrayList.get(arrayList.size() - 1);
//        System.out.println("prev = " + arrayList.get(arrayList.size() - 1).data);
        Pangyo.next = head;
        arrayList.add(newNodeTest); // arrayList : Pangyo - Jeju - tail(Old)

 

 

 

참고
https://st-lab.tistory.com/169