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

문제 설명

나의 풀이

import Foundation
func solution(_ numbers:String) -> Int {
    let data = numbers.map { String($0) }
    var visit = [Bool](repeating: false, count: data.count)
    var answers: Set<Int> = []
    
    func dfs(data: [String], curInd: Int, curCnt: Int, targetCnt: Int, answer: String) {
        if curCnt == targetCnt {
            answers.insert(Int(answer)!)
            return 
        }
    
        for i in 0..<data.count {
            if !visit[i] {
                visit[i] = true
                dfs(data: data, curInd: i, curCnt: curCnt + 1, targetCnt: targetCnt, answer: answer + data[i])
                visit[i] = false
            }
        }
    }
    
    for i in 1...numbers.count {
        dfs(data: data, curInd: 0, curCnt: 0, targetCnt: i, answer: "")
    }
    
    var count = 0
    for num in answers {
        if num < 2 {
            continue
        }
        
        if num == 2 || num == 3 {
            count += 1
        }
        else if isPrimeNumber(num) {
            count += 1
        }
    }
    return count
}


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
}

고민한 점

사실 python에서 사용하는 permutation만 사용할 수 있다면 아주 쉽게 해결이 가능한 문제이다.. 그러나 Swift는 permutation이 없어서 이분의 블로그에서 참고해서 하였다..

permutation, combination 구현좀 해줘라 Swift..😭

괜찮은 남의 풀이

import Foundation

var cache = [String: [String]]()
func permutation(_ array: [String]) -> Set<String> {
    if array.count == 0 { return [] }

    let answerArray = (0..<array.count).flatMap { i -> [String] in
        var removedArray = array
        let elem = removedArray.remove(at: i)
        return [elem] + permutation(removedArray).map { elem + $0 }
    }

    return Set(answerArray)
}

func isPrime(_ number: Int) -> Bool {
    guard number > 1 else {
        return false
    }

    for i in 2..<number {
        if number % i == 0 { return false }
    }
    return true
}

func solution(_ numbers: String) -> Int {
    let array = Array(numbers).map{ String($0) }
    let intSet = Set(permutation(array).compactMap { Int($0) })
    return intSet.filter{ isPrime($0) }.count
}

이 분의 permutation 함수도 잘 이해해봐야겠다.. 어렵구나 고차함수

참고

Programmers