[프로그래머스] (Swift) Kakao - [1차] 캐시 (Lv.2)

🟠 문제 링크

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

프로그래머스

 

🟠 나의 풀이

우선 LRU 알고리즘에 대해서 알아야했다. 진짜 마침,, 마침,, 오늘 아침에 CS 스터디를 했는데 거기서 LRU 알고리즘이 나왔다. 근데 자세한 설명은... 아직 이해하지 않고 넘어간 상태다.. 근데 바로나와 버리다니!!

LRU는 페이징 교체 알고리즘에서 등장한 개념이었다. 
개념은 Least Recently Used로, 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식이다. 큐로 구현되는 방식이고, 사용한 데이터를 큐에서 지우고 맨 위로 데이터를 다시 올리는 방식으로 진행된다. 만약 프레임의 길이가 모자랄 경우, 가장 아래에 있는 데이터를 삭제한다. 

이게 페이징 교체 알고리즘으로 자주 사용되는데, Cache 에서도 사용된다. 마찬가지로, 캐시에서 사용 공간이 부족할 때, 가장 오랫동안 사용되지 않은 항목을 제거하고, 새로운 녀석을 배치하는 형식으로 동작된다. 

그럼, 이걸 어떻게 구현하느냐? LRU가 동작하는 방식은 위에 주황 글씨로 간단하게 설명해두었다. 근데 이해가 잘 안가니, 그림으로 그려보자.

만약 Cache Size 가 3이고, [1, 2, 1, 3, 4, 1, 2, 4]가 참조값이라고 치자. 그럼 LRU 알고리즘은 아래와 같은 방식으로 구현된다.

보면, Caeche Hit 이면, 기존에 있던 해당 값을 삭제하고, 맨 앞 Head에 그 값을 넣는다. 만약, Miss 이면, 그냥 가장 최근값을 Head 에 넣고, 만약 메모리의 size가 3이 넘어가면, 가장 처음에 들어간 데이터를 삭제하면서 길이 3을 유지한다.

 

사실 그림처럼, Caeche 는 실제로 Linked List (head와 tail이 있는 구조)로 구현되어있다고 한다. 그래서 나도 이 문제를 Linked List로 풀어야할까? 고민했는데, 그렇게 하게 되면 코드가 너무 복잡해 질것 같아서, 그냥 머리에 세운 로직을 그대로 for문과 if문을 사용해서 구현했다.

 

🟠 정답코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Programmers/kakao_%EC%BA%90%EC%8B%9C/main.swift

GitHub - deslog/Algorithm: ✨ 백준, 프로그래머스 Swift 문제풀이 ✨

import Foundation

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {

    let newCitiies = cities.map {
        return $0.lowercased()
    }

    var cacheArray = [String]()
    var totalTime = 0

    for city in newCitiies {
        // cache hit
        if cacheArray.contains(city) {
            totalTime += 1
            cacheArray.remove(at: cacheArray.firstIndex(of: city)!)
            cacheArray.append(city)
        } else { // cache miss
            totalTime += 5
            cacheArray.append(city)
            if cacheArray.count > cacheSize {
                cacheArray.removeFirst()
            }
        }
    }
    return totalTime
}