[Swift/프로그래머스] 소수 찾기

frogKing·2022년 6월 1일
0

개요

오랜만에 코딩 문제를 접해서 그런가 머릿속이 컴퓨터화되지 않았나 쉽지 않았다. 이전에 한창 열심히 풀 때는 swift 라이브러리가 파이썬보다 빈약해도 다 구현해버리지 뭐~ 하면서 곧잘 풀었는데 다시 하려니 쉽지 않았다. 어떤 수를 보고 소수를 판별할 때도 어떻게 하나 막혔고, 순열도 구해야 되는데 오랜만에 스택이니 재귀니 하려니 코테는 역시 꾸준히 풀어봐야 하는구나 싶었다.

문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

설명 및 코드

단계로 설명하면 다음과 같다.
1. 문자열을 이용하여 순열을 생성한다. -> permutation
2. 생성한 순열을 바탕으로 소수를 판별한다. -> isPrimeNumber

import Foundation

func solution(_ numbers:String) -> Int {
    func isPrimeNumber(_ num: Int) -> Bool {
        let last = Int(sqrt(Double(num)))
        
        if num == 2 || num == 3 { return true }
        
        guard last >= 2 else { return false }
        
        for i in 2...last {
            if num % i == 0 {
                return false
            }
        }
        
        return true
    }
    
    var p_list = [[Int]]()
    func permutation(_ array: [Int], _ n: Int) {
        
        if array.count < n { return }
        
        var visited = Array(repeating: false, count: array.count)
        
        func cycle(_ now: [Int]) {
            if now.count == n {
                p_list.append(now)
                return
            }
            
            for i in 0...array.count-1 {
                if visited[i] {
                    continue
                } else {
                    visited[i] = true
                    cycle(now + [array[i]])
                    visited[i] = false
                }
            }
        }
        
        cycle([])
    }
    
    let array = numbers.map { Int(String($0))! }
    
    for i in 1...array.count {
        permutation(array, i)
    }
    
    var candidates = Set<Int>()
    for i in p_list {
        let num = Int(i.map{String($0)}.joined())
        candidates.insert(num!)
    }
    
    var result = [Int]()
    for candidate in candidates {
        if isPrimeNumber(candidate) {
            result.append(candidate)
        }
    }
    
    return result.count
}
profile
내가 이걸 알고 있다고 말할 수 있을까

0개의 댓글