프로그래머스 - [1차] 캐시

LRU는 가장 오랫동안 쓰이지 않던 값을 캐시에서 없앤다는 특징이 있습니다

 

LRU란?

LRU는 Least Recently Used 의 약자로 가장 오랫동안 사용되지 않는 값을 지우는 페이지 교체 알고리즘 입니다.

즉 구현하기 위해서는 캐시의 크기를 넘게 값이 들어오게 되면 제일 오래된 값을 비우고 새로운 값을 추가해야합니다.

 

캐시란?

캐시는 메모리와 CPU 간의 속도 차이를 완화하기 위해 메모리의 데이터를 미리 가져와 저장해두는 임시 장소입니다.

필요한 데이터를 미리 가져와 저장하여 새로운 값을 검색할 때 메모리로 값을 찾아가는 대신 캐시를 먼저 확인 후 원하는 데이터를 가져감으로서 속도를 향상시킵니다.

 

캐시 히트: 원하는 데이터를 캐시에서 검색했을 때 존재하는 경우, 해당 데이터를 바로 사용할 수 있게 됩니다.

캐시 미스: 캐시에  원하는 데이터가 없으면 메모리에 가서 찾아야 합니다.

 

문제에서는 캐시 히트인 경우 시간이 1만큼 소요되고 캐시 미스인 경우 5만큼 소요되므로 다음과 같이 구현할 수 있겠습니다.

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

    var recently: [String] = []
    var time = 0
    for city in cities {
        if recently.contains(where: { $0 == city.uppercased() }) {
            recently.removeAll(where: { $0 == city.uppercased() })
            time += 1
        } else {
            time += 5
        }
        recently.append(city.uppercased())
        if recently.count > cacheSize {
            recently.removeFirst()
        }
    }

    return time
}