[Swift 알고리즘] 소수찾기(완전탐색)

 

도망치면 하나, 전진하면 둘

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

프로그래머스

 

 

풀이 방법 : DFS

DFS를 이용해서 푸는데 이거 백트레킹이 필요한 것 아닌가? 어차피 순열을 찾는 것이라 유의미하게 시간을 절약할 수 없다. 만약 입력수가 커지게 된다면 고려해볼만 하지만 최대 7자리기에, 완전탐색이 속편하다고 생각했다.

참고로 백트레킹의 경우

- 앞자리가 0인 경우

- 중복되는 숫자 visited에 이미 원소로 갖고 있을 경우

두가지를 생각해 보았다.

 

코드 

import Foundation

func solution(_ numbers:String) -> Int {
    let targetString = numbers.map{String($0)}
    var targetArr:[String] = []
    var visited:[String] = []
    func dfs(_ dfsArr:[String], _ depth:Int) {
        if visited.count == depth {
            targetArr.append(visited.joined())
            return
        }
        var newArr = dfsArr
        for i in 0 ..< newArr.count {
            let node = newArr.removeFirst()
            visited.append(node)
            dfs(newArr, depth)
            newArr.append(node)
            visited.popLast()
        }
    }
    for i in 1...targetString.count {
        dfs(targetString, i)
    }
    let targetSet = Set(targetArr.map{Int($0)!})
    let maxVal = targetSet.max()!
    var primeArr = Array(repeating: 2, count: maxVal + 1)
    primeArr[1] = 1
    primeArr[0] = 1
    for i in 2 ... maxVal / 2 {
        var tempInd = i    
        while tempInd + i <= maxVal {
            tempInd += i
            primeArr[tempInd] += 1
        }
    }
    
    var resCount = 0
    _ = targetSet.map { cur in
        if primeArr[cur] == 2 {
            resCount += 1
        }
    }
    return resCount
}