[Level 2 / 완전탐색] 소수 찾기 + Swift

소수 찾기

코딩테스트 연습 - 소수 찾기

문제 유형: 완전탐색

1. 소수인지 판별하는 함수

isPrime은 숫자를 받아 소수인지 아닌지 Bool값을 리턴한다.

func isPrime(_ num: Int) -> Bool {
    if(num < 4) { return num < 2 ? false : true }
    for i in 2...Int(sqrt(Double(num))) {
        if(num % i == 0) { return false }
    }
    return true
}

2. 커스텀 순열 함수

permutation 함수는 문자열("1", "2"와 같은 문자열 숫자)로 이루어진 배열과 문자의 길이를 나타내는 targetNum을 받고, 숫자들을 만들어 반환한다. visited는 방문했는지를 나타내는 Bool 타입의 배열이다. 0으로 시작하면 targetNum의 길이를 채우지 못하므로 안된다. 또한 중복은 제외시키고, number가 0이 들어가는 걸 방지하고, 마지막으로 소수일 때, 해당 모든 조건을 충족할 때 result에 해당 숫자를 넣는다.

func permutation(_ array: [String], _ targetNum: Int) -> [Int] {
    var result: [Int] = []
    var visited: [Bool] = Array(repeating: false, count: array.count)
    
    func permute(_ now: String) {
        if now.count == targetNum {
            let number = Int(now)!
            if !now.hasPrefix("0") && !result.contains(number) && isPrime(number) {
                result.append(number)
            }
            return
        }
        for i in 0..<array.count {
            if visited[i] { continue }
            visited[i] = true
            permute(now + array[i])
            visited[i] = false
        }
    }
    permute("")

    return result
}

3. solution함수

numArr은 numbers를 쪼갠 배열이다. $0은 Character 타입이므로 String타입으로 변환한다. 위의 permutation함수에서 나온 숫자들을 result에 추가한다. primeNums와 result에 중복되는 요소들은 없기에(위의 함수에서 중복 없앰), 바로 추가해도 된다. 그 후 result에 반환한다.

func solution(_ numbers:String) -> Int {
    let numArr = numbers.map({ String($0) })
    var result: [Int] = []
    
    for i in 1...numbers.count {
        let primeNums = permutation(numArr, i)
        result += primeNums
    }

    return result.count
}