[Algorithm/Programmers] 캐시 Swift

캐시 - 2018 카카오 1차 / Level 2

문제 풀이:

• 캐시 교체 알고리즘인 LRU(Least Recently Used)를 사용한다.
• 대소문자를 구분하지 않는다.
• hit일 경우 실행시간은 1로 계산하며, miss일 경우 5로 계산한다.
• 큐를 이용한다.

 

1. 대소문자를 구분하지 않기 때문에 도시들을 소문자로 바꿔준다.

2. 캐시의 사이즈가 0일 경우 도시의 수만큼 5를 곱해서 리턴한다.

3. 해당 순서의 도시가 캐시에 없을 경우 (miss)

3-1. 도시를 캐시에 넣어준다.

3-2. 캐시가 가득 찼다면 가장 오래된 데이터를 제거해주고 넣어준다.

3-3. 실행시간을 5만큼 더해준다.

4. 해당 순서의 도시가 캐시에 있을 경우 (hit)

4-1. 캐시에서 해당 도시의 데이터를 꺼내고 제일 앞으로 옮겨준다.

4-2. 실행시간을 1만큼 더해준다.

 

코드: 

import Foundation

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    
    let cities = cities.map { $0.lowercased() }
    var cache = [String]()
    var cnt = 0
    
    if cacheSize == 0 {
        return cities.count * 5
    }
    
    for i in 0..<cities.count {
        if !cache.contains(cities[i]) {
            if  cache.count < cacheSize {
                cache.append(cities[i])
            } else {
                cache.removeFirst()
                cache.append(cities[i])
            }
            cnt += 5
        } else {
            let cacheIndex = cache.firstIndex(of: cities[i])!
            let temp = cache.remove(at: cacheIndex)
            cache.append(temp)
            cnt += 1
        }
    }
    
    return cnt
}

print(solution(3, ["Jeju","Pangyo","Seoul","NewYork","LA","Jeju","Pangyo","Seoul","NewYork","LA"])) // 50
print(solution(2, ["Jeju", "Pangyo", "NewYork", "newyork"])) // 16

 

문제:

programmers.co.kr/learn/courses/30/lessons/17680

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