소수 만들기

• 메모이제이션, dfs, 3중 for문 등을 생각하였다.
• 숫자의 갯수가 50가지라 dsf(= O(2^50))으로는 시간이 오래 걸릴 것 같았다.
• 50^3인 for문으로 접근하였다.
• 소수를 판별하는 것이 중요했는데, 메모이제이션과 비슷한 에라토스테네스의 체를 이용하였다.
• kotlin의 for문에서 ..과 until 사용법을 다시 익혔다.

class Solution {
    val MAX_NUM = 3001
    var mIsPrimeNumber = Array(MAX_NUM){true}

    fun makeEratos() {
        mIsPrimeNumber[0] = false
        mIsPrimeNumber[1] = false
        for (i in 2..MAX_NUM step(1)) {
            if (i * i > MAX_NUM) break
            if (mIsPrimeNumber[i]) {
                for (j in (i * i)..MAX_NUM step(i)) {
                    if (j > MAX_NUM) break
                    mIsPrimeNumber[j] = false
                }
            }
        }
    }
    fun solution(nums: IntArray): Int {
        var answer = 0
        makeEratos()

        for (i in nums.indices) {
            for (j in i + 1 until(nums.size)) {
                for (k in j + 1 until nums.size) {
                    if ((mIsPrimeNumber[nums[i] + nums[j] + nums[k]])) {
                        answer++
                    }
                }
            }
        }
        return answer
    }
}