양의 정수 n
이 주어집니다. 이 숫자를 k
진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
0P0
처럼 소수 양쪽에 0이 있는 경우P0
처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P
처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P
처럼 소수 양쪽에 아무것도 없는 경우P
는 각 자릿수에 0을 포함하지 않는 소수입니다.P
가 될 수 없습니다.예를 들어, 437674을 3진수로 바꾸면 211
02
0101011
입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 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 |
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.
import Foundation
func solution(_ n:Int, _ k:Int) -> Int {
var primeCount = 0
let kNumber: String = String(n, radix:k)
for num in kNumber.split(separator: "0") {
if isPrime(Int(num) ?? -1) {
primeCount += 1
}
}
return primeCount
}
func isPrime(_ number: Int) -> Bool{
if number==1 {
return false
}
if number<=3 {
return true
}
let N: Int = Int(sqrt(Double(number)))
for n in 2...N {
if number%n == 0 {
return false
}
}
return true
}
문제 풀이는 3가지 과정으로 진행된다.
1. 입력으로 주어진 양의 정수 n
을 k
진수로 변환한다.
2. 변환한 k
진수를 문자"0"
으로 파싱 한다.
3. 파싱 한 숫자를 소수 판별한다.
그러면 각 과정을 세부적으로 살펴본다.
우선 k 진수로 변환하는 방법은 String 이니셜라이저를 사용한다. 인자인 radix
에 변환 하고자하는 정수를 넣어준다. 예를 들어 2진수로 변환하고 싶으면 radix에 2를 할당한다. 변환된 값은 문자열로 반환된다.
let kNumber: String = String(n, radix:k)
문자열을 파싱 하는 방법은 split
메소드를 이용한다. 파싱 하고자 하는 구분자를 seperator
인자에 할당하면 된다. 반환 값은 Substring
타입이다. 소수 판별을 위해 필요한 파라미터의 값은 Int
타입이다. 그러나 파싱 된 값이 Substring
이므로 형 변환을 하였다. 이때 옵셔녈 병합 연산자(??
)을 사용하였는데, 이는 Int
타입의 이니셜라이저를 호출할 때 "keke"
와 같이 잘못된 입력값이 들어올 수 있기 때문에 이니셜라이저의 결과로 optional 타입을 반환한다.
for num in kNumber.split(separator: "0") {
if isPrime(Int(num) ?? -1) {
primeCount += 1
}
}
다음은 소수를 구하는 코드이다. 소수를 구하는 방법은 Trial division 방법을 이용하였다.
func isPrime(_ number: Int) -> Bool{
if number==1 {
return false
}
if number<=3 {
return true
}
let N: Int = Int(sqrt(Double(number)))
for n in 2...N {
if number%n == 0 {
return false
}
}
return true
}