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

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

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

kakao 2022 블라인드 코딩테스트

십진수 n을 k진수로 변환한 숫자 j가 있다고 하자.

j를 이루는 각 자리수를 0으로 구분지어 얻을 수 있는 수 중 소수인 수의 개수를 구하는 문제

 

접근방법

우선 n을 k진수로 변환한다. 그런데 Int가 아니라 자리수를 순서대로 담은 String으로 변환한다. getBaseKStringfrom함수가 그것이다.

그렇게 얻은 kString을 0을 기준으로 구분한다. components메서드를 사용했다. 0을 기준으로 구분한 것이기 때문에 00 처럼 0이 연속될 경우 빈 문자열도 생긴다. 따라서 components로 얻어진 배열을 filtering하여 빈 문자열을 걸러낸다.

그러면 이제 소수인지 아닌지 판별할 수만 배열에 들어있다. 물론 현재는 문자열타입이다. 이를 Int로 변환한다. (map을 사용했다.)

그럼 이제 정말 소수인지 아닌지 판별한 Integer들이 배열에 담겨있다. 이 배열을 filtering한다. predicate는 isPrime함수다.

 

오답노트

isPrime함수에서 나누는 수를 최악의 경우 n-1까지 검사하도록 했더니 테스트케이스1번이 시간초과가 났다.

sqrt를 사용해서 풀었다. swift는 암묵적 자료형 변환을 허용하지 않기 때문에 타입변환을 좀 많이 했다.

 

소스코드

import Foundation


func getBaseKStringFrom(_ dec:Int, _ k:Int) -> String {
    var result:String = ""
    var _dec:Int = dec
    
    while _dec > 0 {
        result = "\(_dec % k)" + result
        _dec /= k
    }
    
    return result
}

func isPrime(_ n:Int) -> Bool {
    if n < 2 {
        return false
    } else if n <= 3 {
        return true
    }
    
    
    for d in 2...(Int(sqrt(Double(n)))) {
        if n % d == 0 {
            return false
        }
    }
    
    return true
}

func solution(_ n:Int, _ k:Int) -> Int {
    let kString:String = getBaseKStringFrom(n, k)
    let PList:[Int] = kString.components(separatedBy:"0").filter{ $0.count > 0 }.map{ Int($0) ?? 0 }.filter{ isPrime($0) } 
    
    return PList.count
}