2018 KAKAO BLIND RECRUITMENT [1차] 캐시

해당 문제는 kotlin 을 지원하지는 않지만, Deque를 공부하던 중 Deque를 연습하기 좋은 문제인 것 같아 풀어봤습니다.

테케 및 유추 할 수 있는 최악의 케이스를 넣어 봤습니다.

fun main() {
   var s = System.currentTimeMillis()
   val one = solution(3,arrayOf<String>("Jeju", "Pangyo", "Seoul", "NewYork", "LA",
   "Jeju", "Pangyo", "Seoul", "NewYork", "LA"))
   var e = System.currentTimeMillis()
   println("1실행시간: ${(e-s)/1000.0} 결과값 : ${one}")
   
   var s2 = System.currentTimeMillis()
   val two = solution(3,arrayOf<String>("Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo",
   "Seoul", "Jeju", "Pangyo", "Seoul"))
   var e2 = System.currentTimeMillis()
   println("2실행시간: ${(e2-s2)/1000.0} 결과값 : ${two}")
   
   var s3 = System.currentTimeMillis()
   val three = solution(2,arrayOf<String>("Jeju", "Pangyo", "Seoul", "NewYork", "LA",
   "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"))
   var e3 = System.currentTimeMillis()
   println("3실행시간: ${(e3-s3)/1000.0} 결과값 : ${three}")
   
   var s4 = System.currentTimeMillis()
   val four = solution(5,arrayOf<String>("Jeju", "Pangyo", "Seoul", "NewYork", "LA", 
   "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"))
   var e4 = System.currentTimeMillis()
   println("4실행시간: ${(e4-s4)/1000.0} 결과값 : ${four}")
   
   var s5 = System.currentTimeMillis()
   val five = solution(2,arrayOf<String>("Jeju", "Pangyo", "NewYork", "newyork"))
   var e5 = System.currentTimeMillis()
   println("5실행시간: ${(e5-s5)/1000.0} 결과값 : ${five}")
   
   var s6 = System.currentTimeMillis()
   val six = solution(0,arrayOf<String>("Jeju", "Pangyo", "Seoul", "NewYork", "LA"))
   var e6 = System.currentTimeMillis()
   println("6실행시간: ${(e6-s6)/1000.0} 결과값 : ${six}")
   
   var tempArray = arrayOf<String>()
   var count = 0
   var tempList = listOf<String>("Jeju", "Seoul", "NewYork", "LA", "SanFranciscoSanFranc",
   "Seoul", "RomeRomeRome", "ParisParisParis", "NewYork", "Rome","Jeju", "Seoul",
   "NewYork", "LA", "SanFranciscoSanFranc", "Seoul", "RomeRomeRome", "ParisParisParis",
   "NewYork", "Rome") // size = 20
   while(true){
       tempArray = tempArray.plus(tempList[count%20])
       count++
       if(count == 100000) break
   }
  	
   //매우 성의 없이 제작한 최악의 케이스
   var s7 = System.currentTimeMillis()
   val seven = solution(30,tempArray)
   var e7 = System.currentTimeMillis()
   println("7실행시간: ${(e7-s7)/1000.0} 결과값 : ${seven}")
   
}

fun solution(cacheSize: Int, cities: Array<String>): Int {
    var answer = 0
    if(cacheSize == 0) {
        return cities.size*5
    } else {
        var cache = ArrayDeque<String>()
        for(i in 1 .. cacheSize){
            answer += 5
            val city = cities[i-1].uppercase()
            cache.addFirst(city)
        }

        for(i in cacheSize .. cities.size-1){
            if(cache.contains(cities[i].uppercase())){
                answer += 1
                cache.remove(cities[i].uppercase())
                cache.addFirst(cities[i].uppercase())
            } else {
                answer += 5
                cache.addFirst(cities[i].uppercase())
                if(cache.size > cacheSize) cache.removeLast()
            }
        }

    }
    return answer
}

1실행시간: 0.023 결과값 : 50

2실행시간: 0.001 결과값 : 21

3실행시간: 0.0 결과값 : 60

4실행시간: 0.001 결과값 : 52

5실행시간: 0.0 결과값 : 16

6실행시간: 0.0 결과값 : 25

7실행시간: 0.11 결과값 : 100120

 

상기 문제는 프로그래머스에서 kotlin을 지원하지는 않지만 Deque를 공부하기에 좋았던 문제였습니다.