[문제 풀이] 캐시 (Python, Swift)

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

해결 과정

이 문제는 페이지 교체 알고리즘 중 LRU(Least Recently Used)을 구현하는 문제다. LRU가 무엇인지 그림을 통해 다시 이해하고 queue로 구현하여 해결했다. 특수한 케이스들에 대해서도 처리해야 했는데, 이는 제한조건에도 나와있지만, 주어진 테스트 케이스 5, 6번을 통해서도 알 수 있었고 이를 기반으로 수정하여 해결했다.

 

나의 풀이

Python

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    queue = deque()

    for city in cities:
        city = city.lower()
        if city in queue:
            queue.remove(city)
            queue.append(city)
            answer += 1
        else:
            if len(queue) < cacheSize:
                queue.append(city)
            elif queue:
                queue.popleft()
                queue.append(city)
            answer += 5

    return answer

 

Swift

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    
    var answer = 0
    var cache : [String] = []
    
    for c in cities {
        let city = c.lowercased()
        if cache.contains(city) {
            cache.remove(at: cache.firstIndex(of: city)!)
            // cache = cache.filter {$0 != city}
            cache.append(city)
            answer += 1
        } else {
            if cache.count < cacheSize {
                cache.append(city)
            } else if cache.count > 0 {
                cache.removeFirst()
                cache.append(city)
            }
            answer += 5
        }
    }
    return answer
}

다른 풀이

 

 

IDEA