[프로그래머스] 소수 찾기 with Swift

안녕하세요. 오늘은 프로그래머스 소수 찾기 문제를 풀어보겠습니다.

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

 

이 문제는 재귀를 이용한 완전탐색을 통해 소수판별 알고리즘을 적용하여 문제를 해결 하실 수 있습니다!

 

 우선 순서가 상관없으니 순열을 적용해야합니다.

 

순열은 재귀의 for문에 0부터 시작하면 순열입니다! (순서가 상관있다면 이전 index를 가져와서 index+1부터 탐색하시면 됩니다.)

 

또한 모두 안뽑아도 되고 모두 뽑아도 되므로 해당 숫자가 들어가있을때 한번 안들어가있을때 한번 재귀해줍니다.

 

그 후 소수가 아닌지 맞는지 판별해주시면 되는데요!

 

소수는 신기하게도 square까지만 확인해보면 된다고 합니다!

 

수학적인 증명도 쉽게 가능하니 다들 한번 해보셔도 좋을듯합니다!

 

이렇게 하시고 정답에는 중복이 허용이 안되므로 Set을 이용하여 Set에 Insert해주시고 count를 반환해주면 문제가 해결됩니다!

 

import Foundation

var isVisited:[Int] = [Int]()
var numbersString:[String] = [String]()
var answer = "0"
var count = 0
var answerSet:Set<Int> = Set<Int>()

func isPrimeNumber(_ value: String) {
    let number = Int(value)!
    
    if number < 2 { 
        return
    }
    if number < 4 {
        answerSet.insert(number)
        return
    } 
    
    let last = Int(sqrt(Double(number)))
    for i in 2...last { 
        if number % i == 0 {
            return
        } 
    }
    
    answerSet.insert(number)

}

func permutation() {
    var allVisited = true
    for i in isVisited {
        if i == 0 {
            allVisited = false
            break
        }
    }
    
    if allVisited == true {
        isPrimeNumber(answer)
        return
    }
    
    for i in 0..<numbersString.count {
        if isVisited [i] == 0 {
            isVisited[i] = 1
            answer = answer + numbersString[i]
            permutation()
            answer = String(answer[answer.index(answer.startIndex, offsetBy:0)..<answer.index(answer.endIndex, offsetBy:-1)])
            permutation()
            isVisited[i] = 0
        }
    }
}
func solution(_ numbers:String) -> Int {
    
    for i in 0..<numbers.count {
        numbersString.append((String(numbers[numbers.index(numbers.startIndex, offsetBy: i)])))
        isVisited.append(0)
    }
    
    permutation()

    return answerSet.count
}

 

 

오늘은 여기까지이며, 궁금한 점이 있으시다면 댓글로 남겨주세요.

 

좋은 하루 되세요!