[프로그래머스] level 2 [1차] 캐시 (JS)

문제 링크 : 코딩테스트 연습>2018 KAKAO BLIND RECRUITMENT>[1차] 캐시

---

입력 형식

• cacheSize : 캐시 크기
• 정수, 범위 0 ≤ cacheSize ≤30
• cities : 도시 이름으로 이뤄진 문자열 배열
  • 길이 : 100,000
  • 원소 : 공백, 숫자, 특수 문자 등이 없는 영문자. 대소문 구분 X, 최대 20자

출력 형식

• 입력된 도시이름을 배열 순서대로 처리할 때, “총 실행시간” 출력

조건

• LRU(Least Recently Used) 사용
• cache hit : 실행 시간 1
• cache miss : 실행 시간 5

LRU(Least Recently Used)

• 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식
• 캐시가 가득 찻을때 가장 오랫동안 참조 되지 않는 페이지 제거
• 새로 참조 할때 마다 리스트 맨 앞에 페이지 번호 추가
  • 리스트에 해당 페이지 번호가 없다면 맨 앞에 페이지 번호 추가 → Miss
  • 리스트에 해당 페이지 번호가 있다면 기존 것 제거하고 맨 앞에 페이지 번호 추가 → Hit
  • 캐시가 3이라고할때, 리스트 길이가 4이상이 되면 맨마지막 요소 제거

Cache Hit : CPU가 참조하고자하는 메모리가 캐시에 존재하는 경우
Cache Miss : CPU가 참조하고자하는 메모리가 캐시에 존재하지 않은 경우

Hit Ratio : Cache Hit / (Cache Hit + Cache Miss)
Miss Ratio : Cache Miss / (Cache Hit + Cache Miss)
※ 위의 예시 : Hit Ratio = 3/8, Miss Ratio = 5/8

코드

배열로 구현

function solution(cacheSize, cities) {
    let answer = 0;
    let LUR = [];
    for (let city of cities) {
        city = city.toLowerCase();
        let i = LUR.indexOf(city);
        if (i !== -1) {
            LUR.splice(i, 1);
            answer += 1;
        } else {
            answer += 5;
        }
        LUR.push(city);
        if (LUR.length > cacheSize) LUR.shift();
    }
    return answer;
}

이중 연결 리스트(Doubly Linked List)로 구현

function solution(cacheSize, cities) {
    let answer = 0;
    let dll = new DLL();

    for (let city of cities) {
        city = city.toLowerCase();
        let isNode = dll.get(city);
        if (isNode) {
            if (isNode.index !== 0) {
                dll.remove(isNode.node);
                dll.unshift(city);
            }
            answer += 1;
        } else {
            answer += 5;
            dll.unshift(city);
        }

        if (dll.length > cacheSize) dll.pop();
    }

    return answer;
}

class Node {
    constructor(val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class DLL {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    pop() {
        let node = this.tail;
        if (!this.head) return undefined;
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            node.prev.next = null;
            this.tail = node.prev;
            node.prev = null;
        }
        this.length--;
        return node;
    }

    unshift(val) {
        let newNode = new Node(val);
        if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

    get(val) {
        let index = 0;
        let cur = this.head;
        while (index < this.length) {
            if (cur.val === val) return { 'node': cur, 'index': index };
            cur = cur.next;
            index++;
        }
        return null;
    }

    remove(node) {
        if (this.length === 0) return undefined;
        if (node.next === null) {
            this.pop();
        } else {
            let removedNode = node;
            let prevNode = node.prev;
            let nextNode = node.next;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;

            removedNode.next = null;
            removedNode.prev = null;
            this.length--;
        }
    }
}