[프로그래머스 92335] k진수에서 소수 개수 구하기 swift

문제 설명

 

문제 풀이

0을 기준으로 P를 파악한다. 0P0, 0P, P0, P 형태 모두 가능

즉, 211020101011이 있으면 0을 기준으로 잘라주면 된다.

-> 211, 2, 1, 1, 11 

그 후 숫자들을 소수인지 아닌지 판별해주면 된다.

 

다만 이 문제의 핵심은 시간 복잡도이다.

소수를 구할 때 36이면 1~36모두 돌려서 나머지가 0인걸 찾으면 시간초과가 난다.

 

36의 약수를 보면

2 4 6 9 18

 

36의 제곱근인 6을 기준으로 짝을 이룬다.

따라서 n의 제곱근까지만 for문을 돌려줘도 소수인지 아닌지 판별 가능하다.

 

 

코드

func solution(_ n:Int, _ k:Int) -> Int {
    
    func isPrime(_ num: Int) -> Bool {
        if num < 2 {
            return false
        }
        if num == 2 || num == 3 {
            return true
        }
        
        // 제곱근까지만 검사해도 소수인지 판별 가능
        let s = Int(sqrt(Double(num)))
        for i in 2...s {
            if num % i == 0 {
                return false
            }
        }
        return true
    }
    // k진수로 변환 (String(n, radix: ))
    let num = String(n, radix: k)
    
    // 0을 기준으로 숫자를 나눔
    let nums = num.split(separator: "0").map {Int(String($0))!}
    var answer = 0
    
    for n in nums {
        if isPrime(n) {
            answer += 1
        }
    }
    return answer
}

 

 

후기

풀이시간: 35분

 

1.

테스트케이스 1번에서 시간초과가 났다. 소수 구하는 로직에서 해결하려다가 결국 힌트를 보고.. 제곱근을 이용해 소수를 구해 해결

아마 힌트 없으면 생각 못했을 것 같다..🫠

소수 구하는 건 외워두는게 나을듯

 

2.

외울 함수들

 

k진수 변환

ex) 10을 2진수로 변환

String(10, radix: 2)

 

제곱근 구하기

sqrt(36) 

-> 6

 

제곱 구하기

pow(3, 2) 

-> 9