완전탐색_Programmgers_소수 찾기 [swift]

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

접근방법

1. 주어진 입력String을 [Int]로 변환
2. 만들 수 있는 모든 경우의 수를 전부 생성
3. 모든 경우의 수 각각에 대하여 2~자기자신 까지 나머지 연산(%)을 수행.
4. 반복 중 나머지 연산 결과 값이 0 이 아니었고, 자기자신을 나눌 차례가 되면 소수로 판별

정답코드

import Foundation

func recursive(targetLength: Int, currentSelection: [Int], rests: [Int]) -> Set<Int> {
    if currentSelection.count == targetLength {
        let _output = currentSelection.map{ String($0) }.joined()
        let output = Int(_output)!
        return [output]
    }
    var tempResult: Set<Int> = []
    for (index,selection) in rests.enumerated() {
        var nextRests = rests
        let selection = nextRests.remove(at: index)
        let result = recursive(
            targetLength: targetLength, 
            currentSelection: currentSelection + [selection], 
            rests: nextRests
        )
        tempResult = tempResult.union(result)
    }
    
    return tempResult
}

func solution(_ numbers:String) -> Int {
    let papers: [Int] = numbers.map { $0.wholeNumberValue! }
    
    var posible: Set<Int> = []
    
    for targetLength in 1...numbers.count {
        // nNumber자리수 를 가지는 숫자 조합을 뽑아야함.
        
        for selectIndex in 0...(papers.count - 1) {
            var restNumbers = papers
            let selection = restNumbers.remove(at: selectIndex)
            let result = recursive(
                targetLength: targetLength, 
                currentSelection: [selection], 
                rests: restNumbers
            )
            posible = posible.union(result)
        }
        
    }
    var solList = [Int]()
    for target in posible {
        guard target != 1  else { continue }
        guard target != 0  else { continue }
        for i in 2...target {
            if i == target { solList.append(target) }
            guard target % i != 0 else { break }
            
        }
        
    }
    
    return solList.count
}

아쉬운 점

숫자들 중 n개를 뽑아서 n 자리 수를 만드는 건 순열이다.

그런데, 순열의 쉬운 구현 방법이 생각나지 않았다. 그래서 익숙한 재귀로 모든 경우의 수를 만들어냈다...

성능

테스트 1 〉	통과 (0.50ms, 16.6MB)
테스트 2 〉	통과 (49.41ms, 16.8MB)
테스트 3 〉	통과 (0.17ms, 16.7MB)
테스트 4 〉	통과 (12.28ms, 16.4MB)
테스트 5 〉	통과 (66.27ms, 16.3MB)
테스트 6 〉	통과 (0.65ms, 16.5MB)
테스트 7 〉	통과 (0.99ms, 16.5MB)
테스트 8 〉	통과 (90.81ms, 16.6MB)
테스트 9 〉	통과 (0.23ms, 16.5MB)
테스트 10 〉	통과 (644.74ms, 16.6MB)
테스트 11 〉	통과 (20.25ms, 16.4MB)
테스트 12 〉	통과 (3.53ms, 16.6MB)

더 좋은 고수의 풀이

초-깔끔

import Foundation

var cache = [String: [String]]()

func combinations(_ 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] + combinations(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(combinations(array).compactMap { Int($0) })
    return intSet.filter{ isPrime($0) }.count
}