99클럽 코테 스터디 4기 23일차 TIL - 프로그래머스: 소수 찾기(42839) Swift

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
프로그래머스	42839	소수 찾기	완전탐색	Lv.2	Swift

🚀 나의 접근 방법

숫자 종이 개수가 최대 7로 경우의 수가 많지 않아 완전탐색으로 진행했다.

DFS로 숫자 종이로 만들 수 있는 숫자의 모든 경우를 탐색했다. 탐색하면서 해당 숫자가 소수인지를 확인하여 result Set 자료형(중복이 있기 때문)에 담았다.

소수를 판별하는 함수를 직접 구현해야 한다. 가장 기본적인 방법으로 구현했다. (O(N))

결국 result에 담긴 요소의 개수가 답이 된다.

✍️ 나의 코드

Swift

import Foundation

func solution(_ numbers:String) -> Int {
    let nums = numbers.map{ String($0) }
    
    func isPrimeNum(_ n: [String]) -> Bool {
        guard let num = Int(n.joined()) else { return false }
        if num <= 1 { return false }
        if num <= 3 { return true }
        if num % 2 == 0 { return false }
        for i in 2..<sqrt(num) {
            if num % i == 0 { return false }
        }
        return true
    }
    
    var result: Set<Int> = []
    var visited = Array(repeating: false, count: nums.count)
    
    func dfs(_ nnum: [String]) {
        for (i, num) in nums.enumerated() {
            if nnum.isEmpty && num == "0" { continue }
            var newNum = nnum + [num]
            if !visited[i] {
                visited[i] = true
                if isPrimeNum(newNum) {
                    result.insert(Int(newNum.joined())!)
                }
                dfs(newNum)
                visited[i] = false
            }
        }
    }
    dfs([])
    return result.count
}

🤔 회고

소수(Prime Number) 판별

이번에는 가장 기본적인 소수 판별 알고리즘을 사용했다. 하지만 O(N)으로 판발하려는 숫자가 클수록 비효율적이다.

그래서 에라토스테네스의 체와 같은 알고리즘이 존재한다. 시간초과를 대비하여 학습해 두자.

참고 : 어떤 수가 소수(Prime Number)인지 아닌지 판별하는 다양한 알고리즘