04/18 알고리즘 공부(95) - 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 함수를 완성해 주세요.

제한조건

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입출력 예

n	k	result
437674	3	3
110011	10	2

알고리즘 예상

1. toString(k)를 이용해 k진수로 바꾼다.
2. split("0")과 filter룰 이용해 0을 기준으로 진수를 나눈 후 1과 비어있는 원소를 모두 지운다.
3. map{it.toInt()}를 이용해 숫자로 바꿔준다.
4. count{ (1..k).count{ k % it 0 } == 2 }를 이용해 소수 갯수를 구해준다.  

 

초기 코드

class Solution {
    fun solution(n: Int, k: Int): Int {
        var answer: Int = -1
        return answer
    }
}

 

내 코드

// 테스트 케이스 통과, 실패(시간초과)
class Solution {
    fun solution(n: Int, k: Int): Int = n.toString(k)
        .split("0")
        .filter { it != "" }
        .map { it.toLong() }
        .count { long1 ->
            (1..long1).count { long1 % it == 0L } == 2
        }
}

int타입으로 했더니 런타임에러가 나서 long으로 바꿨지만 이번에는 시간초과가 발생한다. 반복 횟수를 줄이기 위해 제곱근으로 바꿔야겠다.

import kotlin.math.sqrt

class Solution {
    fun solution(n: Int, k: Int): Int = n.toString(k)
        .split("0")
        .filter { it != "" }
        .filter { it != "1" }
        .map { it.toLong() }
        .count { long1 ->
            (2..sqrt(long1.toDouble()).toLong()).count { long1 % it == 0L } == 0
        }
}

제곱근으로 바꿨을 때 1에 대한 처리가 힘들어 filter를 이용해 제거했다. 정상적으로 작동하고 성공했다.

다른 사람의 풀이

// 지금은 실패가 뜨지만 처음보는 방법이라 가져와봤다.
import java.math.*
class Solution {
    fun solution(n: Int, k: Int): Int {
        var answer: Int =0
        val newN = n.toString(k).split("0")
        for(i in newN) {
            if(i == "" || i == "0" || i == "1") continue
            if(BigInteger(i).isProbablePrime(1)) answer ++
        }
        return answer
    }
}

 

개선점 또는 배운점

1. 자바의 BigInteger 클래스의 메서드 중 isProbablePrime이라는 메서드는 확률적 소수 판별법인 밀러-라빈 소수판별법을 실행해서 소수인지 확인하는 메서드이다.