[Lv. 1] 소수 만들기

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12977

 

난이도 : Level.1

언어 : Kotlin

 

문제 설명 :

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항 : 

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예 :

nums	result
[1, 2, 3, 4]	1
[1, 2, 7, 6, 4]	4

풀이 : 

import kotlin.math.sqrt

class Solution {
    var answer = 0
    
    fun solution(nums: IntArray): Int {
        combination(0, 3, 0, nums, mutableListOf())
        return answer
    }
    
    fun combination(cnt: Int, depth: Int, startAt: Int, arr: IntArray, temp: MutableList<Int>) {
        if (cnt == depth) {
            if (isPrime(temp.sum())) answer++
        } else {
            for (i in startAt until arr.size) {
                temp.add(arr[i])
                combination(cnt + 1, depth, i + 1, arr, temp)
                temp.removeAt(temp.lastIndex)
            }
        }
    }
    
    fun isPrime(n: Int): Boolean {
        if (n <= 1) return false
        return (2 .. sqrt(n.toDouble()).toInt()).none { n % it == 0 }
    }
}

 

조합을 사용해 3가지를 뽑은 경우의 수를 구해내고 그 값들을 하나로 더한 값으로 하여금 소수인지 아닌지 판별하여 소수라면 answer가 더해지는 형식