[프로그래머스] Swift - k진수에서 소수 개수 구하기 (LV.2)

👆문제풀러 가기👆

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

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

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 `P0` 형태에서 찾을 수 있으며, 2는 `0P0`에서, 11은 `0P`에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

 

입출력 예제

n	k	result
437674	3	3
110011	10	2

 

 

 

풀이 [ 메모리: 16.5mb, 최대시간:  0.03ms ] 

func solution(_ n:Int, _ k:Int) -> Int {
    let radix = String(n, radix: k)
    let values = radix.split(separator: "0").compactMap { Int($0) }
    var count = 0
    
    for value in values {
        if checkPrimeNumber(value) {
            count += 1
        }
    }
    
    return count
}

func checkPrimeNumber(_ num: Int) -> Bool {
    if num < 2 { return false }
    if (2...3) ~= num { return true }
    
    for i in 2...Int(sqrt(Double(num))) {
        if num % i == 0 {
            return false
        }
    }
    
    return true
}

문제를 받고 생각한 것.

1. n을 k진수로 변환하기 위해 Radix 함수 활용
2. P0, 0P, 0P0 등을 구분하기 위해 split을 활용해 0을 기준으로 구분하기
3. 구분된 값들이 소수인지 판별하기
4. 소수 갯수 세기