[프로그래머스/Swift] 92335번 - k진수에서 소수 개수 구하기

풀이

형태에 대한 풀이를 먼저 하겠다

• 조건을 보면 형태가 4가지 (0p0, p0, 0p, p)라고 생각할 수 있지만, 생각을 달리 해보면 (p0, p)로 이루어져 있다.
• 예) p0p0p0의 경우 우선 p0 한번 찾으면 p0p0가 되고 이것은 다시 p0가 되는 식이다
• 예제) 437674의 3진수인 211020101011를 우선 P0인 2110을 제외 하면 20101011 이고, 이 숫자는 다시 P0의 형태를 띄는것을 알 수 있다 (물론, 이때 P0는 사실 0P0 이지만)
• 이제 우린 0만 찾으면 되고 0이 없다면 그 숫자는 P형태가 될것이고 0이 있다면 거기까지 숫자를 P0 형태를 찾은것이다

형태에 대한 풀이는 위의 내용이면 충분하고 소수를 찾는 방법을 설명해보자

• 일반적으로 소수를 찾는 방법을 쓸때는 에라토스테네스의 체를 사용한다 (https://ko.wikipedia.org/wiki/에라토스테네스의_체)
• 하지만 이 문제의 경우 잘 생각해보면 굳이 소수를 전부 찾지 않아도 된다
• 처음에 0이 나오는 경우는 없고, 끝에 0이 나오면 이미 그 수는 10분의 1이 된다. 정말 만약 중간에 0이 나오면? 그수는 100분의 1수로 줄어든다 그러면 사실상 시간은 넉넉하다. 만약에 0이 안나오면? 그 숫자 하나만 소수를 판단하면 된다 ⇒ 그래서 P가 구해지면 P가 소수인지만 구하기로 했다.
• P가 소수인지는 2부터 P의 제곱근까지 직접 나누기로 했다

import Foundation

func solution(_ n:Int, _ k:Int) -> Int {
    //진수 변경
    var result: Int = 0 // 조건에 부합하는 P의 개수
    let num: [String] = String(n, radix: k).map{ String($0) }
    var idx: Int = 0
    var numberStr: String = ""
    var strToInt: Int = 0
    while idx < num.count {
        if num[idx] == "0" { // 0 을 만난경우 여기서 부터 새로운 P0찾기
            strToInt = Int(numberStr) ?? 0
            if checkPrime(strToInt) { result += 1 }
            numberStr = ""
        }
        numberStr += num[idx]
        idx += 1
    }
    if numberStr != "" {
        strToInt = Int(numberStr) ?? 0
        if checkPrime(strToInt) { result += 1 }
    }
    return result
}
func checkPrime(_ number: Int) -> Bool { // 소수 판별
    if number == 0 || number == 1 { return false }
    if number == 2 || number == 3 { return true}
    // 4부터 정상작동
    let num: Double = Double(number)
    for i in 2...Int(sqrt(num)) {
        if number % i == 0 { return false}
    }
    return true
}