[프로그래머스/Kotlin] 소수 만들기

문제 링크 -> https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

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

제한사항

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

------------------------------------------------------------풀이------------------------------------------------------------------
* 3개수를 조합하기위해 재귀함수를 사용합니다. 
* 모든 경우의 수를 확인해야되기 때문에 완전탐색을 합니다. 

1. combi 재귀함수를 설계합니다.
 - combi함수는 nums, 방문한 곳을 표시할 visit, index시작지점 start, 방문한 곳의 갯수를 표시할 count를 인자로 받습니
   다. 
 - 재귀함수는 방문한 곳의 boolean값을 true로 변경하면서 탐색합니다. 방문한 곳에서 나왔다면 false로 변경합니다.
 - 방문한 곳의 수가 3개라면 방문한 곳의 value를 더해 수를 조합합니다.
 - 조합한 수가 소수라면 answer에 +1합니다.
2. 소수를 판별한 prime을 설계합니다.
 - 소수는 약수가 1과 자기 자신, 즉 약수로 2개만을 가진 수입니다. 

class Solution {
    var answer = 0
    fun solution(nums: IntArray): Int {
        var visit = Array<Boolean>(nums.size){false}
        combi(nums, visit, 0, 0)
        return answer
    }

    fun combi(numbers : IntArray, visit : Array<Boolean>, start : Int, count : Int){
        if( count == 3){
            var sum = 0
            for( i in 0..visit.size-1){
                if(visit[i]){
                    sum+=numbers[i]
                }
            }
            if(prime(sum)) {
                answer+=1
            }
            return
        }
        else{
            for(i in start..numbers.size-1){
                visit[i] = true
                combi(numbers, visit, i+1, count+1)
                visit[i] = false
            }
        }
    }

    fun prime(num : Int) : Boolean {
        for( i in 2..num/2){
            if(num%i == 0){
                return false
            }
        }
        return true
    }
}

------------------------------------------------------------결과------------------------------------------------------------------

재귀함수를 설계할 수 있고, 소수가 무엇인지 안다면 금방 풀 수 있는 문제네요 

다른사람 풀이에서 훨씬 간단하게 풀이하신분이 있는데 역시 저는 멀었나 봅니다.. ㅜㅜ 








- 문제에 대한 질문 댓글 환영!
- 중간에 잘못된 부분이 있다면 댓글로 남겨주세요. 수정하겠습니다.