코딩테스트 연습 - [1차] 캐시

문제 풀이 아이디어

LRU

문제에서 주어진대로 그대로 구현하면 되는 문제입니다. 다만 LRU(Least Recently Used)가 무엇인지 알고 있어야 하는데요. LRU는 OS를 배울 때 나온 페이지 교체의 기법 중에 하나로 캐시의 용량이 가득 찼을 때 마지막으로 사용된 페이지를 삭제하고 새로운 페이지를 저장하는 기법입니다.

Array

우리는 Array 자료형을 가지고 캐시를 구현할 예정입니다. LRU 방식을 구현하기 위해서 array의 도시들은 최근에 처리된 순서대로 정렬되도록 유지합니다. 즉 가장 앞에 있는 도시가 LRU, 즉 가장 예전에 처리된 도시인 것이죠.

새로운 도시가 처리할 때 array 안에 도시가 있다면 true를 리턴하고 해당 도시를 일단 삭제한 후 다시 추가합니다. (가장 최근에 처리된 도시가 뒤로 가야 합니다.)

만약 새로운 도시가 array 안에 없다면 false를 리턴하고 해당 도시를 array의 맨 뒤에 추가합니다. 이 때 만약 array의 크기가 주어진 cache_size를 초과한 경우 맨 처음 도시를 삭제해줍니다. (LRU)

시간복잡도

위 설명과 아래 코드를 보면 아시겠지만 Array의 원소를 추가하고 삭제하는 일이 빈번하게 일어납니다. Array에 원소를 추가하는 것은 O(1)이지만 Array의 가장 첫 원소를 삭제하는 것은 O(N) (N은 Array의 길이)입니다. 시간복잡도를 걱정하지 않을 수 없습니다. 하지만 문제에 주어진 조건을 보면 캐시의 크기는 최대 30입니다. 따라서 우리가 array에서 삭제할 때 시간복잡도는 최대 O(30)이라고 볼 수 있습니다.

Big O에서 상수는 O(1)과 같습니다. 따라서 이 경우 시간복잡도에 대해서 크게 걱정할 필요는 없습니다.

🙌 문제를 풀 때는 오히려 역으로 캐시의 최대 크기가 30이라는 것을 보고 “Array의 삭제를 사용해도 되겠구나”라는 힌트를 얻을 수 있어야 한다고 생각합니다.

코드

코드의 가독성을 높이기 위해서 캐시 구조체를 따로 선언해서 구현해봤습니다.

// 캐시 구조체
struct Cache {
    private var data = [String]()
    private let size: Int

    init(size: Int) {
        self.size = size
    }
    
    // 캐시가 히트 했는지 알아보는 함수
    mutating func isHit(_ city: String) -> Bool {
        // 히트했다면?
        if data.contains(city) {
            // 해당 city를 가장 마지막 index로 옮겨주기
                //🚫 참고로 swap하면 안되고 지우고 append해주어야 함 (swap하면 LRU의 원칙에 어긋남)
            let cityIndex = data.lastIndex(of: city)!
            data.remove(at: cityIndex)
            data.append(city)
            return true
        // 미스 했다면?
        } else {
            // 캐시에 도시 추가
            data.append(city)
            // 캐시 용량 다 찼다면 LRU한 도시(= data의 가장 첫 도시)를 삭제
            if data.count > size {
                _ = data.removeFirst()
            }
            return false
        }
    }
}

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    
    var ans = 0
    var cache = Cache(size: cacheSize)
    
    for city in cities {
        // 대소문자 구분 하지 않으므로 소문자로 모두 바꾸기
        if cache.isHit(city.lowercased()) {
            ans += 1
        } else {
            ans += 5
        }
    }
    
    return ans
}