2024.05.21 TIL 코트카타 58번(소수 만들기)

class Solution {
    fun solution(nums: IntArray): Int {
        var answer = 0

        selectElelements(nums, 3, IntArray(3), 0, 0)

        for(combination in combinationList) {
            var addedNums = 0
            for(num in combination) {
                addedNums += num
            }
            if(isSosu(addedNums))
                answer++
        }
        return answer
    }
    
    fun findSosu(nums: IntArray): Int {
        var answer = 0

        selectElelements(nums, 3, IntArray(3), 0, 0)

        for(combination in combinationList) {
            var addedNums = 0
            for(num in combination) {
                addedNums += num
            }
            if(isSosu(addedNums))
                answer++
        }

        return answer
    }

    val combinationList = mutableListOf<IntArray>()
    fun selectElelements(nums: IntArray, r: Int, selectedNums: IntArray, selectedNumsIndex: Int, currentNumsIndex: Int): Unit{

        if(selectedNumsIndex == r) {
            var copiedSelectedNums = IntArray(r)

            for(selectedIndex in 0..r-1) {
                copiedSelectedNums[selectedIndex] = selectedNums[selectedIndex]
            }

            combinationList.add(copiedSelectedNums)

        } else if(nums.size == currentNumsIndex) {
            return
        } else {
            selectedNums[selectedNumsIndex] = nums[currentNumsIndex]
            selectElelements(nums, r, selectedNums, selectedNumsIndex+1, currentNumsIndex+1)
            selectElelements(nums, r, selectedNums, selectedNumsIndex, currentNumsIndex+1)
        }

        return

    }

    fun isSosu(num: Int): Boolean{

        if(num <= 1)
            return false

        var sqrtedNum = Math.sqrt(num.toDouble())
        for(underSqrtNum in 2..sqrtedNum.toInt()) {
            if(num % underSqrtNum == 0)
                return false
        }

        return true
    }
}

 

포인트

- 조합(Combination)을 활용한 완전탐색

- 소수를 구할 때 2~해당수의 제곱근까지 약수가 있는지 확인