전역 변수를 활용해서 시간 단축하기

https://school.programmers.co.kr/learn/courses/30/lessons/12943

프로그래머스

 

이 문제에 대한 해답은 주어진 문제의 로직을 따라 작성하면 어렵지 않게 구할 수 있다.

다만 8,000,000에 3을 6번 곱하면 2,147,483,647을 넘기 때문에, Long으로 변환한 후 계산해줘야 한다.

class Solution {
    fun solution(num: Int): Int {
        var answer = 0
        var n = num.toLong()
        while (n != 1L && answer < 500) {
            if (n % 2 == 0L) {
                n /= 2L
            } else {
                n = n * 3L + 1L
            }
            answer += 1
        }
        return if (answer < 500) {
            answer
        } else {
            -1
        }
    }
}

 

 

이게 정말 최선의 정답인지 비슷한 문제를 찾아봤다.

 

https://leetcode.com/problems/sort-integers-by-the-power-value/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

 

1이 되는 숫자를 구하는 더 빠른 로직은 없었다.

 

import java.util.*

class Solution {

    data class Num(
        val num: Int,
        val index: Int,
        val power: Int,
    )
    private val memo = HashMap<Int, Int>()

    private fun countPower(num: Int): Int {
        if (num in memo) {
            return memo[num]!!
        }

        val count = if (num % 2 == 0) {
            countPower(num / 2) + 1
        } else {
            countPower(num * 3 + 1) + 1
        }
        memo[num] = count
        return count
    }

    fun getKth(lo: Int, hi: Int, k: Int): Int {
        memo[1] = 0
        val results = Array<Num>(hi-lo+1) { i ->
            Num(lo+i, i, countPower(lo+i))
        }
        results.sortWith { num1, num2 ->
            if (num1.power == num2.power) {
                num1.index - num2.index
            } else {
                num1.power - num2.power
            }
        }

        return results[k-1].num
    }
}

 

특이한 부분

내가 작성한 코드는 260~320ms가 걸렸는데, 137ms가 걸린 더 빠른 코드가 있었고, GPT에게 차이점을 찾아달라고 요청했다.

https://chat.openai.com/share/ec7b1a5b-fd39-476a-844e-a55970faadb8

ChatGPT

 

차이점은 가능한 모든 숫자(1 ~ 1000)의 횟수를 미리 계산해서 static으로 선언하는 것이였다.

지금까지 각 테스트케이스는 서로 영향을 주지 않는다고 생각했는데, 필요한 값을 미리 계산해서 companion object에 넣어둠으로써 영향을 줄 수 있었다.

 

class Solution {

    data class Num(
        val num: Int,
        val index: Int,
        val power: Int,
    )

    fun getKth(lo: Int, hi: Int, k: Int): Int {
        var countInRange = 0
        for (i in 0 until 1000) {
            if (results[i].num in lo..hi) {
                countInRange++
            }
            if (countInRange == k) {
                return results[i].num
            }
        }
        return -1
    }

    companion object {
        private val memo = hashMapOf<Int, Int>(1 to 0)

        lateinit var results: Array<Num>

        init {
            results = Array<Num>(1000) { i ->
                Num(i+1, i, countPower(i+1))
            }
            
            results.sortWith { num1, num2 ->
                if (num1.power == num2.power) {
                    num1.index - num2.index
                } else {
                    num1.power - num2.power
                }
            }
        }

        private fun countPower(num: Int): Int {
            if (num in memo) {
                return memo[num]!!
            }

            val count = if (num % 2 == 0) {
                countPower(num / 2) + 1
            } else {
                countPower(num * 3 + 1) + 1
            }
            memo[num] = count
            return count
        }
    }
}