문제
문제 설명
양의 정수 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 함수를 완성해 주세요.
제한사항
- 1 ≤ n ≤ 1,000,000
- 3 ≤ k ≤ 10
입출력 예
| n | k |
|---|---|
| 437674 | 3 |
| 110011 | 10 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.
제한시간 안내
- 정확성 테스트 : 10초
풀이
나의 풀이
- n을 k진수로 바꾸기
- 0을 기준으로 나누기(split)
- 소수 구해서 개수 리턴하기
import Foundation
func solution(_ n:Int, _ k:Int) -> Int {
var result = 0
let split = String(n, radix: k).split(separator: "0").map { Int($0)! } // k진수 변환 후 0 split
let filter = split.filter { $0 != 1 } // 1 제외
// 소수 구하기
filter.forEach { num in
var prime = true
for i in 2...Int(sqrt(Double(num))) + 1 {
if num % i == 0 && i != num { // 자기 자신이 아닌 수로 나누어 떨어지면
prime = false
break
}
}
if prime {
result += 1
}
}
return result
}| 정확성 | 테스트 | 정확성 | 테스트 |
|---|---|---|---|
| 테스트 1 〉 | 통과 (14.28ms, 16.4MB) | 테스트 2 〉 | 통과 (0.10ms, 16.2MB) |
| 테스트 3 〉 | 통과 (0.10ms, 16.4MB) | 테스트 4 〉 | 통과 (0.14ms, 16.5MB) |
| 테스트 5 〉 | 통과 (0.10ms, 16.4MB) | 테스트 6 〉 | 통과 (0.11ms, 16.3MB) |
| 테스트 7 〉 | 통과 (0.10ms, 16.4MB) | 테스트 8 〉 | 통과 (0.11ms, 16.3MB) |
| 테스트 9 〉 | 통과 (0.12ms, 16.2MB) | 테스트 10 〉 | 통과 (0.11ms, 16.5MB) |
| 테스트 11 〉 | 통과 (0.11ms, 16.2MB) | 테스트 12 〉 | 통과 (0.11ms, 16.2MB) |
| 테스트 13 〉 | 통과 (0.11ms, 16.4MB) | 테스트 14 〉 | 통과 (0.10ms, 16.3MB) |
| 테스트 15 〉 | 통과 (0.10ms, 16.3MB) | 테스트 16 〉 | 통과 (0.12ms, 16.6MB) |
다른 사람의 풀이
로직은 내 풀이와 유사하다. 하지만 다른 점이 있다면 소수를 찾는 부분이다. 나는 for 문을 이용해서 2부터 제곱 근까지 반복하며 소수를 찾는데, 자기 자신이 아닌 수로 나누어지면 break 하여 그 뒤에 수는 검사하지 않는다.
아래 풀이에서는 while 문을 이용했고 2부터 제곱 근까지 쭉 검사한다. 그래서 테스트 결과의 실행 시간을 보면 미세하게 내 풀이가 빠른 걸 볼 수 있다. 아마 이 부분 때문에 차이가 나지 않았나 싶다.
그래도 아래 풀이는 따로 함수를 만들어서 더 깔끔하다.
import Foundation
func solution(_ n: Int, _ k: Int) -> Int {
let s = String(n, radix: k)
return s.split(separator: "0").filter { p in !p.isEmpty && p != "1" && isPrime(Int(p)!) && (s.contains("0\(p)0") || s.contains("\(p)0") || s.contains("0\(p)") || s.contains(p)) }.count
}
private func isPrime(_ n: Int) -> Bool {
var i = 2
while i <= Int(sqrt(Double(n))) {
guard n % i != 0 else {
return false
}
i += 1
}
return true
}| 정확성 | 테스트 | 정확성 | 테스트 |
|---|---|---|---|
| 테스트 1 〉 | 통과 (18.01ms, 16.2MB) | 테스트 2 〉 | 통과 (0.12ms, 16.2MB) |
| 테스트 3 〉 | 통과 (0.13ms, 16.7MB) | 테스트 4 〉 | 통과 (0.12ms, 16.3MB) |
| 테스트 5 〉 | 통과 (0.12ms, 16.3MB) | 테스트 6 〉 | 통과 (0.14ms, 16.7MB) |
| 테스트 7 〉 | 통과 (0.14ms, 16.6MB) | 테스트 8 〉 | 통과 (0.11ms, 16.3MB) |
| 테스트 9 〉 | 통과 (0.17ms, 16.4MB) | 테스트 10 〉 | 통과 (0.12ms, 16.4MB) |
| 테스트 11 〉 | 통과 (0.10ms, 16.3MB) | 테스트 12 〉 | 통과 (0.10ms, 16.5MB) |
| 테스트 13 〉 | 통과 (0.12ms, 16.4MB) | 테스트 14 〉 | 통과 (0.10ms, 16.2MB) |
| 테스트 15 〉 | 통과 (0.10ms, 16.4MB) | 테스트 16 〉 | 통과 (0.15ms, 16.4MB) |
정리
⏰
목표 풀이 시간 : 1시간
실제 풀이 시간 : 46분
정답률 : 55.82%
이 문제는 2021년 9월에 진행된 2022 KAKAO BLIND RECRUITMENT 1차 코딩 테스트에 출제된 문제로 총 7문제 중 두 번째로 출제되었다.
해설
이 문제는 진법 변환 후에 변환된 숫자를 0을 기준으로 파싱하고, 파싱 한 숫자를 소수 판별해 해결할 수 있는 문제입니다.
소수 판별하는 데에는 대표적으로 2가지 방법이 있습니다. 첫 번째로 에라토스테네스의 체가 있고, 두 번째는 어떤 수 n을 2부터 루트(n)까지 나눈 나머지가 모두 0이 아님을 확인하는 방법이 있습니다. 효율적인 소수 판별 알고리즘인 에라토스테네스의 체를 사용해서도 풀 수 있지만, 이 문제에서는 두 번째 방법으로도 충분히 해결할 수 있습니다.
이 문제의 제한사항을 살펴보면 n이 1부터 1,000,000까지이고 k는 3부터 10까지이므로, 1,000,000을 3진수로 바꾸면 1,212,210,202,001입니다. 일반적으로 진법 변환은 문자열을 사용해 구현하므로, 진법 변환된 문자열을 0을 기준으로 파싱 한 후에 소수를 판별하는 과정에서 정수 자료형으로 변환이 필요하게 됩니다. 이때, 개발 언어에 따라서 int 자료형의 표현 범위를 벗어날 수 있음을 유의해서 문제를 풀어야 합니다. 예를 들어 997,244를 3진수로 바꾸면 1,212,122,221,222가 됩니다. 이 숫자는 0이 없기 때문에 진법 변환된 숫자 그대로 정수 자료형으로 변환해서 소수 판별을 해야 하는데, 이는 int 자료형의 표현 범위를 벗어난다는 것을 알 수 있습니다.
후기
이번 문제는 레벨 2 치고 쉬웠다. 오히려 레벨 1 문제가 더 오래 걸렸다. 하지만 한 가지 놓친 게 있다면 제한사항을 간과했다는 점이다. 해설을 보고 알았는데, int 범위를 벗어날 수도 있으니 이에 유의해야 한다는 점이다. 문제를 풀면서 전혀 이 부분에 대한 문제를 생각하지 않고 풀었다. 다행이라 하기엔 애매하지만 실행했을 때 에러가 나지 않아서 잘 푼 줄 알았다.
다음부턴 문제 설명뿐만 아니라 제한사항까지 꼼꼼히 살펴보면서 코딩하자!👊
