완전탐색 알고리즘 (dfs)를 통해서 주어진 숫자로 만들 수 있는 모든 경우의 수를 탐색하고 해당 숫자가 소수인지 판정해서 소수이면 숫자를 세면 됩니다.
카드를 일부만 사용할 수도 있으므로 별도의 탈출 조건 없이 dfs를 통해 탐색할 때 마다 모든 숫자가 소수인지 아닌지 판정을 합니다.
“011”과 “11”의 경우 같은 숫자로 취급하므로 소수들을 집합에 넣어서 중복은 제거하도록 합시다.
추가적으로 numbers를 그대로 string 배열로 사용해도 되지만 Swift는 Int ↔ String의 비용이 큽니다. 왠만하면 형변환을 최소화하는 방법으로 구현하도록 합니다.
import Foundation
// 소수임을 알아보는 extension
extension Int {
var isPrim: Bool {
// 1보다 작거나 같은 수는 소수가 아니다.
if self <= 1 { return false }
// 2 ~ (self - 1) 중에 나누어 떨어지는 수가 있으면 false
for i in 2..<self {
if self % i == 0 { return false }
}
return true
}
}
func solution(_ numbers:String) -> Int {
// dfs 구현
func dfs(_ now: Int) {
// 소수인지 확인하고 소수이면 집합에 넣는다.
if now.isPrim {
prims.insert(now)
}
// 완전 탐색
for i in 0..<nums.count {
if !visited[i] {
visited[i] = true
dfs(now * 10 + nums[i]) //👉 새로운 숫자카드를 기존 숫자 뒤에 붙인다
visited[i] = false
}
}
}
// 입력을 숫자들의 배열로 만든다.
let nums = numbers.map { Int(String($0))! }
// 중복제거를 위해 집합을 사용한다.
var prims = Set<Int>()
var visited = Array(repeating: false, count: nums.count)
dfs(0)
return prims.count
}
처음에 소수를 구하는 extension을 이렇게 구현하니 시간초과가 나더라구요. 1과 자신 이외에 나누어 떨어지는 수가 없는 수라는 소수의 정의에 너무 매몰된 구현입니다.
위 처럼 중간에 나누어 떨어지는 수가 있으면 바로 return false하는 백트래킹을 사용해야 합니다.
import Foundation
extension Int {
var isPrim: Bool {
if self <= 1 { return false }
var cnt = 0
for i in 2...self {
if self % i == 0 { cnt += 1 }
}
return cnt == 1 ? true : false
}
}