Swift) 프로그래머스(Lv2) - 소수 찾기 (Brut-Force)

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

안녕하세요 후르륵짭짭 입니다.

간단한 완전 탐색 문제 입니다.

저는 조합으로 풀었는데, 여기서 챙기고 싶은 것은 저의 방법이 구리고

다른 사람은 간단하게 Set 방법을 이용했다는 겁니다.

 

** 저의 코드 **

var check : [Bool] = []
var answer : Int = 0
var dictionary : [Int] = []

func solution(_ numbers:String) -> Int {
        
    let numberList = Array(numbers).map { (char) -> String in
        return String(char)
    }
    
    check = Array(repeating: false, count: numberList.count)
    
    for times in 1...numberList.count{
        DFS(0, 0, times, "", numberList)
    }
    
    return answer
}

func DFS(_ current : Int,_ currentindex : Int ,_ maxPic : Int,_ sum : String ,_ numList : [String]){
    
    if current == maxPic {
        if checkisPrim(Int(sum)!) {
            
            if !dictionary.contains(Int(sum)!){
                print(Int(sum)!)
                    answer += 1
                dictionary.append(Int(sum)!)
            }
        
        }
    }
    else{
        
        for index in 0..<check.count {
        
            if check[index] == false{
                check[index] = true
                DFS(current + 1 , index + 1, maxPic, sum + numList[index], numList )
                check[index] = false
            }
            
        }
    
    
}
    
}
    
    func checkisPrim(_ num : Int) ->  Bool{
        
        if num <= 1{
            return false
        }
        
        if num > 3 {
            
        for index in 2...Int(sqrt(Double(num))){
            
            if num % index == 0 {
                return false
            }
            
        }
            
        }
        
        return true
    }

저의 코드는 그냥 일반 적인 방법인데,,,,

너무 많은 공간을 활용한다는 단점이 있습니다.

조합에서 사용 될 Check 변수랑 중복 체크를 위한 dictionary 변수,,,

건저 갈게 있다면  소수 탐색 함수 입니다.

    func checkisPrim(_ num : Int) ->  Bool{
        
        if num <= 1{
            return false
        }
        
        if num > 3 {
            
        for index in 2...Int(sqrt(Double(num))){
            
            if num % index == 0 {
                return false
            }
            
        }
            
        }
        
        return true
    }

 

** 다른 사람의 코드 ** 

var sol3Array : [Int] = []

func solution3(_ numbers:String) -> Int{
    
    let array = Array(numbers).map { (char) -> String in
        return String(char)
    }
    
    let size = array.count
    var cnt = 0
    newDFS(size, array, 0, "")
    
    let setList = Array(Set(sol3Array))
    
    for element in setList{
        if checkisPrim(element) {
            cnt += 1
        }
    }
    
    return cnt
}

func newDFS(_ size: Int, _ numbers : [String], _ depth : Int, _ value : String){
    
    var tempNumbers = numbers
    
    if size > depth {
        
        for i in 0..<numbers.count{
            
            let item = tempNumbers[i]
            tempNumbers.remove(at: i)
            sol3Array.append(Int(value + item)!)
            newDFS(size, tempNumbers, depth + 1, value + item)
            tempNumbers.insert(item, at: i)
            
        }
        
    }
    
}

다른 분의 코드를 제가 다시 바꿔서 짰습니다.

여기서 코드는 중복 체크를 Set으로 했다는 겁니다. 

Set(배열)을 넣어주면 타입이 Set.배열타입 이 됩니다.

그래서 이 Set에 Array를 해주면 Set이 적용된 배열 타입형 배열이 완성이 됩니다.

또한 탐색을 위해 새로운 배열인 check 함수를 만들어 줄 필요 없이 

        for i in 0..<numbers.count{
            
            let item = tempNumbers[i]
            tempNumbers.remove(at: i)
            sol3Array.append(Int(value + item)!)
            newDFS(size, tempNumbers, depth + 1, value + item)
            tempNumbers.insert(item, at: i)
            
        }

Swift의 배열 특징인 삭제와 삽입을 이용해서 조합 문제를 해결 할 수 있습니다.

물론 시간은 좀 더 걸리겠지만, 훨씬 보기 쉽고 간편하다고 생각 합니다.