[프로그래머스] 완전탐색 - 소수 찾기 (Swift 풀이)

조합 구하기

먼저, 주어진 숫자 카드로 만들 수 있는 모든 조합을 구해야 한다.

카드 조합의 가능한 최대 길이는 카드의 개수와 같다.

자리수의 조합이므로, Int형으로 다루는 것 보다 String형으로 다루는 것이 +연산자를 사용하여 편리하게 구현할 수 있을 것이다.

Swift에서는 문자열 그 자체로 다루는 것 보다, 문자열을 배열 형태로 변환하여 사용하는 것이 더 편리할 것이다.

조합을 구하는 함수는 반환형을 String을 요소로 갖는 Set로 하는게 좋겠다.

Int형이라면 맨 앞자리 숫자가 0일 경우 없애버리기 때문에 그 앞에 새로운 숫자를 붙이게 될 경우, 

1+01 => 101이 아니라, 1+01 -> 11이 되어버릴 것이기 때문이다.

 

조합을 구할 때 재귀를 사용하면 좋겠다.

n자리수 숫자 조합을 구하려면

1. 반복문을 통해 숫자 카드 하나를 먼저 선택한 다음

2. 그  숫자카드를 제외한 모든 카드로 n-1자리 숫자 조합을 구한다.

3. 아까 선택한 숫자카드 뒤에 n-1자리 숫자 조합을 각각 붙인다.

 

이와 같은 로직으로 구현하면 될 것이다. 

재귀의 탈출 조건은, 1자리수 숫자 조합을 구하려고 하면, 카드 하나하나의 숫자 집합을 반환하면 된다.

 

 

소수 구하기

1부터 자기 자신까지 모든 수로 나누었을 때 나누어 떨어지는 숫자가 1과 자기자신 뿐인 숫자를 소수라고 한다.

그럼 2부터 자기자신보다 1 작은 수로 모두 나누어보면 될 것이다.

사실 모든 수가 아니라, 자기 자신보다 작은 모든 소수로 나누어보면 된다.

사실 자기 자신의 제곱근 이하 숫자까지만 나누어보면 된다.

 

이 문제의 경우, 조합을 구하고 그 조합에서 소수가 몇개인지 구하는 문제인데, 

모든 경우의 수 마다 일일이 나누어주는 것은 비효율적이다.

순차적으로 계산하면서, 중간에 조합에 해당하는 값이 소수라는 결론에 다다르면, 바로 카운트만 1증가시켜주고 이어서 계산하면 된다.

 

import Foundation

func solution(_ numbers: String) -> Int {
    let combinations = comb(digit: numbers.count, numbers: numbers.seperate()).compactMap { 
        return Int($0)
    }
    let answer = primeCount(Set(combinations))
    return answer
}

func comb(digit: Int, numbers: [String]) -> Set<String> {
    if digit == 1 { return Set(numbers) }
    if digit < 1 { return [] }
    
    var answer: Set<String> = []
    for i in 0..<numbers.count {
        let num = numbers[i]
        var subNumbers: [String] = numbers
        subNumbers.remove(at: i)
        
        let subComb = comb(digit: digit-1, numbers: subNumbers)
        let subArray = subComb.compactMap{ num + $0 }
        answer = answer.union(subComb)
        answer = answer.union(Set(subArray))
    }
    
    return answer
}

func primeCount(_ numbers: Set<Int>) -> Int {
    var primes = [Int]()
    var count = 0
    
    // 가장 큰 수의 제곱근까지 모든 소수를 구한다.
    let max = numbers.max() ?? 0
    for i in 2...max.sqrtUp() {
        var isPrime = true
        for prime in primes {
            if i % prime == 0 {
                isPrime = false
                break
            } 
        }
        if !isPrime { continue }
        primes.append(i)
    }
    
    // num의 제곱근 보다 작은 모든 소수로 나누어 떨어지지 않는 수는 소수이다.
    for num in numbers {
        if num < 2 {continue}
        var isPrime = true
        for prime in primes {
            if num.sqrtUp() > prime && num % prime == 0 {
                isPrime = false
                break
            } 
        }
        if isPrime { count += 1 }
    }
    
    return count
}

extension String {
    func seperate() -> [String] {
        let array = self.compactMap{ String($0) }
        return array
    }
}

extension Int {
    func sqrtUp() -> Int {
        let root = sqrt(Double(self))
        return Int(root)+1
    }
}