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

문제 설명

나의 풀이

import Foundation
func solution(_ nums:[Int]) -> Int {
    var answer = 0
    var primeNumbers = [Int]()
    for number in 6...3000 {
        if isPrimeNumber(number) {
            primeNumbers.append(number)
        }
    }
    
    var possibles = [Int]()
    for i in 0..<nums.count-2 {
        for j in i+1..<nums.count-1 {
            for k in j+1..<nums.count {
                possibles.append(nums[i] + nums[j] + nums[k])
            }
        }
    }
    
    for num in possibles {
        if primeNumbers.contains(num) {
            answer += 1
        }
    }
    return answer
}

func isPrimeNumber(_ num: Int) -> Bool {
    let sqrtValue = Double(num).squareRoot()
    let intSqrtValue = Int(sqrtValue)
    
    for i in 2...intSqrtValue {
        if num % i == 0 {
            return false
        }
    }
    return true
}

고민한 점

1. 소수인지를 확인하는 방법 중 하나는 바로 해당 수의 제곱근까지의 수로 해당 숫자를 나눠보는 방법이다.
2. Swift에서 제곱근을 구하는 방법은 .squreRoot()를 사용하면된다. 이때 Double 타입만 가능하며 반환값도 Double이다.
3. Swift에서는 permutation, combination이 전혀 제공되지 않는다… 따라서 이러한 경우에는 직접 구해야한다..

괜찮은 남의 풀이

import Foundation
func solution(_ nums:[Int]) -> Int {
    var answer: Int = 0
    var combi: [Int] = [Int](repeating: 0, count: 3)
    combination(nums, &combi, 0, nums.count, 0, 3, &answer)

    return answer
}

func checkPrime(_ num: Int) -> Bool {
    var index: Int = 0
    for i in 2...num {
        if num % i == 0 {
            index = i
            break
        }
    }
    if index == num {
        return true
    }
    return false
}

func combination(_ nums: [Int], _ combi: inout [Int], _ target: Int,
                 _ n: Int, _ index: Int, _ k: Int, _ answer: inout Int) {
    if k == 0 {
        var checkNum: Int = 0
        for i in combi {
            checkNum += nums[i]
        }
        // 소수이면 1 더함
        if checkPrime(checkNum) {
            answer += 1
        }
    }
    else if target == n {
        return
    }
    else {
        combi[index] = target
        combination(nums, &combi, target + 1, n, index + 1, k - 1, &answer)
        combination(nums, &combi, target + 1, n, index, k, &answer)
    }
}

음 조합을 작성한 코드인데, 이 문제는 조합이 배열 안에서 서로 다른 3개를 고르는 것이고, 내부에 중복된 숫자가 없으므로 조합이 아닌 순열을 사용해야지 맞는거 같은데 조합에서 중독되는 숫자를 어떻게 걸려주고 있는건지는 잘 모르겠다..

참고

Programmers