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

문제 설명

양의 정수 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 함수를 완성해 주세요.

 

예시

    n              k     result

437674	3	3
110011	10	2

 

풀이

문제에 조건이 많아보이지만 간단했다. 단지, 0을 기준으로 수를 나눠서 그 수가 소수인지 판별하면 되는 문제였다. 0을 기준으로 수를 나누면 제외 조건인 수 안에 0을 포함하는 문제는 자동으로 해결되었다. 결국 k진수로 바꾼 뒤 0을 기준으로 수를 나눠 소수인지 판별 후 개수를 리턴하면 되는 문제이다.

k진수로 바꾸기 위해서는 주어진 수를 k로 계속해서 나누며 나머지를 가장 앞쪽에 붙이면 된다. 예를 들어 45라는 수를 2진수로 바꿔보자. 45를 2로 나누면 나머지는 1이다. 계속해서 나머지를 앞쪽에다 붙이면 "101101"이 된다. 

소수를 판별하는 것은 해당 수의 제곱근까지 나눠가면서 나머지가 0인 수가 있으면 false, 아니면 true를 출력하도록 했다.

import Foundation

func solution(_ n:Int, _ k:Int) -> Int {
    
    var number: String = ""
    var tempStr: String = ""
    var tempArr: [String] = []
    var count: Int = 0
    //k진수로 바꾸는 함수
    func changeNum(_ num: Int) -> String {
        
        var temp: String = ""
        var num: Int = num
        var quo: Int = 0
        
        while true {
            if num / k == 0 {
                temp = String(quo) + temp
                break
            }
            temp = String(num % k) + temp
            // 몫인 0인 경우에 while문을 탈출할 것이므로 이전 값을 저장해놨다가 붙일 예정
            quo = num / k
            num = num / k
        }
        return temp
    }
    // 소수 체크 함수
    func isPrime(_ num: Int) -> Bool {
        
        let number: Int = num
        
        if number == 1 {
            return false
        } else if number == 2 || number == 3{
            return true
        } else {
            for i in 2...Int(sqrt(Double(number))) {
                if number % i == 0 {
                    return false
                }
            }
        }
        return true
    }
    
    number = changeNum(n)
    
    for i in number {
        if i != "0" {
            tempStr.append(i)
        } else {
            if tempStr == "" {
                continue
            } else {
                tempArr.append(tempStr)
                tempStr = ""
            }
        }
    }
    //마지막에 tempStr에 있는 수도 넣어줌.
    if tempStr != "" {
        tempArr.append(tempStr)
    }
    //소수인지 판별
    if tempArr.count == 0 {
        return 0
    } else {
        for i in tempArr {
            if isPrime(Int(i)!) {
                count += 1
            }
        }
    }
    return count
}

나는 일단 k진수로 변환하는 함수, 소수 판별하는 함수를 따로 구현하였다. 

change함수로 변환을 한 뒤 number라는 string변수에 담아주었다. 다음으로 number를 한 자리수씩 확인해가며 수를 나눠 배열에 담았다. 이때 i가 "0"인 것으로 조건문을 걸었는데, 무조건 "0"을 만날 때 문자열을 배열에 넣으면 ""인 경우도 생기므로 확인해주었다.

문자열을 전부 탐색하면 가장 마지막에 들어있는 tempStr값은 배열에 추가되지 않기 때문에 따로 추가한 뒤 for문을 통해 소수인지 판별해주었다.

 

결론

이번 문제는 처음에 읽어보았을 때 굉장히 어려워보였지만 어렵지 않게 구현할 수 있었던 문제같다.