Algorithm / k진수에서 소수 개수 구하기

문제

프로그래머스 / k진수에서 소수 개수 구하기

1) 문제 풀이

func solution(_ n:Int, _ k:Int) -> Int {
    let numbers = String(n, radix: k)
    let nums = numbers.split(separator: "0").compactMap { Int($0) }
    var answer = 0
    
    for num in nums {
        if num == 0 || num == 1 {
            continue
        }
                
        for i in 2...num {
            if i == num {
                answer += 1
            }
            
            if num % i == 0 {
                break
            }
        }
    }
    
    return answer
}

결과

2) 코드 개선

⚠️ 문제점 분석

• 소수 판별 알고리즘의 비효율성
  • 현재 방법은 매 num마다 2부터 num까지 나눠보며 소수 여부를 판단한다.
  • 이 때 시간 복잡도는 O(N)
  • 숫자가 커질수록 매우 비효율적이다.
• 불필요한 소수 판별
  • if num == 0 || num == 1 { continue }
  • 위 체크는 맞지만, 소수 판별 함수 안에 넣으면 코드가 더 깔끔해짐
• 오버플로우 가능성(optional 강제 언래핑)
  • Int(String) 변환 시 값이 클 경우 nil이 될 수 있으므로, compactMap은 적절하지만 이후에도 예외 처리에 주의가 필요.

✅ 개선 포인트

• 소수 판별 알고리즘 변경(√num까지만 나눠보는 로직)
• 중복 코드 분리(함수화)
• 코드 가독성 향상

func solution(_ n:Int, _ k:Int) -> Int {
    let converted = String(n, radix: k)
    let candidates = converted.split(separator: "0").compactMap { Int($0) }
    
    func isPrime(_ n: Int) -> Bool {
        if n < 2 { return false }
        if n == 2 { return true }
        if n % 2 == 0 { return false }
        
        let upper = Int(Double(n).squareRoot())
        for i in stride(from: 3, through: upper, by: 2) {
            if n % i == 0 { return false }
        }
        return true
    }

    return candidates.filter { isPrime($0) }.count
}

결과