2018 KAKAO BLIND RECRUITMENT [1차] 캐시 Swift

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

Foma's 풀이

문제풀이

먼저 첫번째로 LRU가 무엇인지 알아봐야할텐데요. 

 

LRU란? -> Least Recently Used 가장 최근에 사용되지 않은 것을 교체한다는 뜻입니다.

 

즉, 가장 오래된 것을 제거한다는 뜻입니다.

 

이 원리를 적용하면 새로운 값이 들어왔을때 가장 마지막 인덱스를 제거되고 가장 첫번째 인덱스에 

 

새로운 값이 들어가게 됩니다.

 

예시로 알아보면 3종류가 들어갈 수 있는 도시들에 (1)제주,(2)판교,(3)뉴욕이 담겨있고 서울이라는 새로운 도시를 넣으려고 하면

 

맨 마지막에 뉴욕이 나가고 맨 첫번째에 서울이 추가되어 (1)서울,(2)제주,(3)판교가 됩니다.

 

그리고 cacheSize는 도시의 종류를 얼만큼 담을 수 있는가입니다.

 

즉, cacheSize가 3이라면 3가지 종류의 도시를 담을 수 있는 것입니다.

 

하지만 새로운 도시가 들어올 때 만약 이미 그 도시가 담겨있다면 어떻게 될까요?

 

이 경우에는 도시들에서 원래 그 도시가 있던 순서가 삭제되고 맨 첫번째에 도시가 추가됩니다.

 

위의 예시와 같이 도시들에 (1)제주,)(2)판교,(3)뉴욕이 담겨있고 판교라는 원래 있던 도시를 넣으려고 하면

 

원래 있던 도시들에서 2번째인 판교가 삭제되고 맨 첫번째에 판교가 추가되어 (1)판교,)(2)제주,(3)뉴욕이 됩니다.

 

이와 같이 원래 있던 도시를 넣으면 cache hit이며 수행시간이 1이 추가되는 것이고

 

새로운 도시를 넣으면 cache miss로 수행시간이 5가 추가되는 것입니다.

코드풀이

캐시들을 담을 배열을 만들어줍니다. -> var cache = [String]()

 

수행시간을 저장할 배열을 만들어줍니다. -> var time = 0

 

도시들(cities)를 for문을 이용하여 하나하나 살펴봅니다. -> for city in cities { ... }

 

문제에서 대소문자 구별을 하지않는다고 했으므로 도시의 모든 문자를 소문자로 바꿔주겠습니다. -> let lowerCity = city.lowercased()

 

만약 cacheSize가 0이라면 도시들이 추가될 때 항상 cache miss이므로 수행시간을 도시들의 갯수 곱하기 5를 해준 뒤 for문을 탈출합니다. - > if cacheSize == 0 {

            time = 5*cities.count

            break

        }

 

만약 캐시안에 이미 도시가 있다면 해당 인덱스를 찾아서 삭제해준뒤 수행시간에 +1을 해줍니다. -> if cache.contains(lowerCity) {

            cache.remove(at: cache.firstIndex(of: lowerCity)!)

            time += 1

        }

 

그렇지 않고(새로운 도시라면) 캐시가 꽉 찼을땐 가장 오래된 값을 삭제해준뒤 수행시간에 +1을 해줍니다. ->

else{

            if cache.count == cacheSize{

                cache.removeLast()

            }

            time += 5

        }

 

그리고 포함되있든 안되있는 가장 첫번째에 도시를 추가해줍니다. -> cache.insert(lowerCity, at: 0)

 

마지막으로 수행시간을 반환해줍니다. ->  return time

 

전체코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

import Foundation   func solution(_ cacheSize:Int, _ cities:[String]) -> Int {     var cache = [String]()     var time = 0     for city in cities {         let lowerCity = city.lowercased()         if cacheSize == 0 {             time = 5*cities.count             break         }         if cache.contains(lowerCity) {             cache.remove(at: cache.firstIndex(of: lowerCity)!)             time += 1         }else{             if cache.count == cacheSize{                 cache.removeLast()             }             time += 5         }         cache.insert(lowerCity, at: 0)     }     return time } Colored by Color Scripter

 

새롭게 알게된것

removeLast와 popLast의 차이

 

removeLast는 만약 배열에 아무것도 없을 때 에러가 나지만 popLast는 아무것도 없으면 nil값을 반환한다.

 

배열안에 특정값의 인덱스 알아내기

 

firstIndex(of:value)