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

문제: https://programmers.co.kr/learn/courses/30/lessons/92335

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

 

이 문제의 풀이 단계는

1. n을 k진수로 변환

2. 주어진 조건에 따라 숫자들을 모아놓고

3. 숫자가 소수인지 판별

 

주어진 조건은 다음과 같습니다. 

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

 

k진수로 바꾸어진 숫자를 0을 기준으로 분리하면 주어진 조건에 맞는 숫자들이 됩니다. 

예를 들어, 437674을 3진수로 바꾸면 211 0 2 0 1 0 1 0 11입니다. 0을 기준으로 분리하면 211, 2, 1, 1, 11이 나옵니다. 여기서 소수인 숫자는 211, 2, 11입니다.

 

코드에서는 n을 k진수로 바꾼 후 split 함수를 통해 0을 기준으로 분리합니다. 분리되어 나온 배열들을 돌며 isPrime 함수로 소수 판별을 진행합니다. 만약 소수라면 결괏값을 +1하고 소수가 아니라면 아무것도 하지 않습니다.

import Foundation

func solution(_ n:Int, _ k:Int) -> Int {
    var dp = [Int: Bool]()
    dp[1] = false
    dp[2] = true
    dp[3] = true
    
    func isPrime(x: Int) -> Bool {
        if dp[x] != nil {
            return dp[x]!
        }
        
        for i in 2...Int(sqrt(Double(x))) {
            if x % i == 0 {
                dp[x] = false
                return false
            }
        }
        
        dp[x] = true
        return true
    }
    
    let str = String(n, radix: k).split(separator: "0")
    var result = 0
    
    for number in str {
        if isPrime(x: Int(number)!) {
            result += 1
        }
    }
    
    return result
}