[Swift 알고리즘] 프로그래머스(Lv.2) - 소수 찾기

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 소수 찾기" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 완전 탐색 문제입니다.

 

숫자 카드로 만들 수 있는 모든 수를 구해서 그것이 소수인지 판별하면 됩니다.

 

String으로 들어온 input을 한 글자씩 Array로 나눕니다.

이 Array를 이용해 길이가 1짜리 숫자, 길이가 2짜리 숫자, ..., 길이가 numbers.count짜리 숫자를 구해야 합니다.

 

permutation(순열)는 재귀를 이용해 구했습니다.

위에서 구한 Array의 index로 방문 여부를 표시하여 다시 추가되는 일이 없도록 했습니다. 

재귀를 들어가기 전 visited[index]를 체크하고 재귀에서 빠져나오면 visited[index]를 해제했습니다.

다음 순서에서는 다시 추가가 되야 하기 때문입니다.

 

만약 원하는 길이만큼 숫자가 추가되었다면 Int로 변환하여 Set에 담아줍니다.

Set에 담는 이유는 숫자의 중복을 효율적으로 지우기 위해서 입니다.

 

마지막에 이 Set의 길이를 return 하면 됩니다.

 

감사합니다!

 

---

전체 코드

import Foundation

func isPrime(_ num: Int) -> Bool {
    if num < 4 {
        return (num <= 1) ? false : true
    } else {
        for i in 2...Int(sqrt(Double(num))) {
            if num % i == 0 {
                return false
            }
        }
    }
    
    return true
}

func solution(_ numbers:String) -> Int {
    let nums: [String] = numbers.map { String($0) }
    var visited: [Bool] = []
    var numSet: Set<Int> = []
    
    func permutation(_ numArr: [String], count: Int, rCount: Int) {
        if count == rCount {
            numSet.insert(Int(numArr.joined())!)
            return
        }
        
        for (i, n) in nums.enumerated() {
            if visited[i] {
                continue
            }
            
            var newNumArr = numArr
            newNumArr.append(n)
            
            visited[i] = true
            permutation(newNumArr, count: count+1, rCount: rCount)
            visited[i] = false
        }
    }
    
    for i in 1...nums.count {
        visited = Array(repeating: false, count: nums.count)
        
        permutation([], count: 0, rCount: i)
    }
        
    return numSet.filter { isPrime($0) }.count
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.