Swift ) 프로그래머스(Lv2) - [1차] 캐시 (Hash)

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

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

안녕하세요 후르륵 짭짭 입니다.

이번에도 카카오 블라인드 채용 문제를 다뤄보도록 하겠습니다.

처음에 풀었는데,,, 2 예제에 대해서 오류가 발생해서,,, 이유를 찾지 못했습니다..

생각으로 예제 케이스를 생각했는데,,, 그것 보다 저의 코드를 깊게 다시 보니

two pointer로 탐색 할때 등호를 안해줘서 틀린 거였습니다.

 

** 저의 코드 **

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    
    let newCities = cities.map { (char) -> String in
        return String(char.lowercased())
    }
    
    print(newCities)
    
    if cacheSize == 0 {
        return cities.count * 5
    }
    
    var currentCache = 0
    var answer = 0
    var dict : [String : Int] = [:]
    var queue : [String] = []
    
    for element in newCities {
        
        var flag = false
        
        if let _ = dict[element] {
            answer += 1
            
            flag = true
        }
        else{
            answer += 5
            dict[element] = 1
        }
        
        //딕셔너리에 존재한다.
        if flag {
            
            var start = 0
            var end = queue.count - 1
            var index = 0
            
            while start <= end {
                
                if queue[start] == element {
                    index = start
                    break
                }
                else if queue[end] == element {
                    index = end
                    break
                }
                
                start += 1
                end -= 1
                
            }
            
            queue.remove(at: index)
            queue.append(element)
            
        }
        //딕셔너리에 존재하지 않다.
        else {
            
            if currentCache >= cacheSize {
            
                let item =  queue.removeFirst()
                dict.removeValue(forKey: item)
                queue.append(element)
            }
            else{
                    
                queue.append(element)
                currentCache += 1
                
            }
        
        }
        
        
    }
    
    
    return answer
}

 

방법은 기존의 방법들과 동일합니다.

일단 딕셔러니를 사용해서 중복 여부를 파악해줬습니다. 그리고 queue를 사용해서 오랫동안 사용하지 않은 것은 앞으로 두었습니다.

만약에 중복된 부분이 있다면, queue에서 현재 요소를 찾아서 맨뒤로 보내야합니다.

그래서 아래 처럼 twoPointer를 사용해서 좀 더 빠른 시간 안에 탐색 할 수 있도록 했습니다.

        if flag {
            
            var start = 0
            var end = queue.count - 1
            var index = 0
            
            while start <= end {
                
                if queue[start] == element {
                    index = start
                    break
                }
                else if queue[end] == element {
                    index = end
                    break
                }
                
                start += 1
                end -= 1
                
            }
            
            queue.remove(at: index)
            queue.append(element)
            
        }

 

그런데 만약에 존재 하지 않다면

캐시가 꽉 찼을 때, 그냥 추가해줍니다.

반면에 꽉 차지 않았다면 맨 앞의 요소를 제거해주고 딕셔너리에서도 제거 해줘야합니다.

     else {
            
            if currentCache >= cacheSize {
            
                let item =  queue.removeFirst()
                dict.removeValue(forKey: item)
                queue.append(element)
            }
            else{
                    
                queue.append(element)
                currentCache += 1
                
            }
        
        }

 

** 다른 사람의 코드 **

윤태종님의 코드

func LRU(ch : [String], city : String, cacheSize : Int) -> [String]{
  var cache = ch

  if cache.contains(city){ cache.remove(at: cache.index(of: city)!) }
  if cache.count == cacheSize{ cache.removeLast() }
  cache.insert(city, at: 0)

  return cache
}

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    var cache = [String]()
    var count = 0

    if cacheSize == 0 { return 5*cities.count }
    else{
      for city in cities{
        let lowedCity = city.lowercased()
        if cache.contains(lowedCity){ count += 1 }
        else{ count += 5 }
        cache = LRU(ch: cache, city: lowedCity, cacheSize: cacheSize)
      }
    }

 return count
}

 

** 새롭게 알게 된 점 **

그런데 새롭게 알게 된 것이 있습니다

var queue : [String] = ["A", "B","C","D","E"]

let a = queue.firstIndex(of: "C")!

queue.remove(at: a)

print(queue)

이렇게 있을 때, firstIndex(of:)로 원하는 요소의 인덱스를 찾아서 반환해줍니다.

이러면 저 처럼 twoPointer를 사용하지 않고 제공 되는 함수로 찾을 수 있습니다.

그런데 firstIndex(of:)는 시간 복잡도가 O(n)이기 때문에 주의해야합니다.

developer.apple.com/documentation/swift/array/2994720-firstindex

Apple Developer Documentation