(Swift) Programmers 소수 찾기

SteadySlower·2022년 9월 30일
0

Coding Test

목록 보기
170/305

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

문제 풀이 아이디어

완전탐색 알고리즘 (dfs)를 통해서 주어진 숫자로 만들 수 있는 모든 경우의 수를 탐색하고 해당 숫자가 소수인지 판정해서 소수이면 숫자를 세면 됩니다.

카드를 일부만 사용할 수도 있으므로 별도의 탈출 조건 없이 dfs를 통해 탐색할 때 마다 모든 숫자가 소수인지 아닌지 판정을 합니다.

“011”과 “11”의 경우 같은 숫자로 취급하므로 소수들을 집합에 넣어서 중복은 제거하도록 합시다.

추가적으로 numbers를 그대로 string 배열로 사용해도 되지만 Swift는 Int ↔ String의 비용이 큽니다. 왠만하면 형변환을 최소화하는 방법으로 구현하도록 합니다.

코드

import Foundation

// 소수임을 알아보는 extension
extension Int {
    var isPrim: Bool {
        // 1보다 작거나 같은 수는 소수가 아니다.
        if self <= 1 { return false }
        
        // 2 ~ (self - 1) 중에 나누어 떨어지는 수가 있으면 false
        for i in 2..<self {
            if self % i == 0 { return false }
        }
        
        return true
    }
}

func solution(_ numbers:String) -> Int {
    // dfs 구현
    func dfs(_ now: Int) {
        // 소수인지 확인하고 소수이면 집합에 넣는다.
        if now.isPrim {
            prims.insert(now)
        }
        
        // 완전 탐색
        for i in 0..<nums.count {
            if !visited[i] {
                visited[i] = true
                dfs(now * 10 + nums[i]) //👉 새로운 숫자카드를 기존 숫자 뒤에 붙인다
                visited[i] = false
            }
        }
    }
    
    // 입력을 숫자들의 배열로 만든다.
    let nums = numbers.map { Int(String($0))! }
    // 중복제거를 위해 집합을 사용한다.
    var prims = Set<Int>()
    var visited = Array(repeating: false, count: nums.count)
    
    dfs(0)
    
    return prims.count
}

시간초과 😭

처음에 소수를 구하는 extension을 이렇게 구현하니 시간초과가 나더라구요. 1과 자신 이외에 나누어 떨어지는 수가 없는 수라는 소수의 정의에 너무 매몰된 구현입니다.

위 처럼 중간에 나누어 떨어지는 수가 있으면 바로 return false하는 백트래킹을 사용해야 합니다.

import Foundation

extension Int {
    var isPrim: Bool {
        if self <= 1 { return false }
        
        var cnt = 0
        
        for i in 2...self {
            if self % i == 0 { cnt += 1 }
        }
        
        return cnt == 1 ? true : false
    }
}
profile
백과사전 보다 항해일지(혹은 표류일지)를 지향합니다.

0개의 댓글