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

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.

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

 

제한사항

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

풀이1

1) 3중 for문으로 나올 수 있는 모든 경우의 합을 구해둔다.

2) 에라토스테네스 체 알고리즘으로 소수판별용 슬라이스를 만든다

3) 해당 슬라이스로 아까 구한 총합들의 소수 여부를 확인하고 answer ++

func solution(nums []int) int {
    answer := 0
    max := 0
    
    var totalSum = make([]int, 0)
    
    //모든 경우의 합을 구함
    for i:=0; i<len(nums) -2; i++ {
       for j:=i+1; j<len(nums) -1; j++ {
            for k:=j+1; k<len(nums); k++ {
                sum := nums[i] + nums[j] + nums[k]
                totalSum = append(totalSum, sum)
                
                if max<sum{
                    max = sum
                }
            } 
        } 
    }
    
    //에라토스테네스의 체 알고리즘으로 소수판별용 슬라이스 만들기
    var isPrime = make([]bool, max+1)
    for i:=2; i<= max; i++{
        if !isPrime[i]{
            for j:=i+i; j<=max; j+=i{
                isPrime[j] = true
            }
        }
    }
    
    //아까 구한 총합들 중 소수 판별
    for i:=0; i<len(totalSum); i++{
        if !isPrime[totalSum[i]]{
            answer++
        }
    }
    
    return answer
}

 

풀이2

1) 3중 for문으로 나올 수 있는 모든 경우의 합을 구한다.

2) 각각 소수 판별

import "math"

func isPrime(num int) bool{
    for i:=2; i<=int(math.Sqrt(float64(num))); i++{
        if num%i ==0{
            return false
        }
    }
    
    return true
}

func solution(nums []int) int {
    answer := 0    
    
    for i:=0; i<len(nums) -2; i++ {
       for j:=i+1; j<len(nums) -1; j++ {
            for k:=j+1; k<len(nums); k++ {
                if isPrime(nums[i] + nums[j] + nums[k]){
                    answer ++
                }          
            } 
        } 
    }
    
    return answer
}