ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2018 KAKAO BLIND RECRUITMENT [1차] 캐시
    프로그래머스 2023. 1. 16. 21:03
    728x90

    해당 문제는 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를 공부하기에 좋았던 문제였습니다.

    '프로그래머스' 카테고리의 다른 글

    [프로그래머스][kotlin]다리를 지나는 트럭  (0) 2023.01.23
    올바른 괄호  (0) 2023.01.18
    크기가 작은 부분 문자열  (0) 2022.12.22
    귤 고르기  (0) 2022.12.21
    할인 행사  (2) 2022.12.19
Designed by Tistory.