프로그래머스 Lv2 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

문제 예시와 같습니다.

입출력 예 #2

110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

---

나의 풀이

우선 10진수를 k 진수를 만드는 것부터 시작해야 한다.

자바 내부 메서드로도 구현이 가능한데 이것부터 알아보자면 다음과 같이 사용할 수 있다.

public class Solution {
    public static void main(String[] args) {
        // 테스트를 위한 10진수 값 = 25
        int a = 25;

        System.out.println("10진수 -> 2진수");
        System.out.println(Integer.toBinaryString(a)); // 11001
        System.out.println(Integer.toString(a,2)); // 11001

        System.out.println("10진수 -> 3진수");
        System.out.println(Integer.toString(a,3)); // 221

        System.out.println("10진수 -> 4진수");
        System.out.println(Integer.toString(a,4)); // 121

        System.out.println("10진수 -> 5진수");
        System.out.println(Integer.toString(a,5)); // 100

		    ...
    }
}

Integer.toString(n, x) (n은 10진수, x는 x진수)사용을 통해서 쉽게 구현이 가능하다.

하지만 직접 알고리즘을 구현하는 쪽이 훨씬 재밌으니까 알고리즘을 구현해보자!

while (n > 0) {
            str = String.valueOf(n % k) + str;
            n /= k;
        }ㅇ

ㅇㅇ알고리즘 역시 간단하다. 10진수 숫자 n을 숫자를 k로 나눈 나머지를 역순으로 저장하고 n을 k로 나눠준 값을 반환한다. 2진수로의 변환을 예로 들면

• 13 % 2 = 1 / 13 / 2 = 6
• 6 % 2 = 0 / 6/ 2 = 3
• 3 % 2 = 1 / 3 / 2 = 1
• 1 % 2 = 1 / 1 / 2 = 0.5 종료)

위의 과정을 거쳐 “1101”이 되는 것이다.

이를 적용한 풀이는 다음과 같다.

import java.util.Arrays;

class Solution {
    int answer = 0;

    public int solution(int n, int k) {
        String str = "";

        while (n > 0) {
            str = String.valueOf(n % k) + str;
            n /= k;
        }
        String[] nums = str.split("0");

        for (String s : nums) {
            if (s.equals("")) continue;
            if (checkPrime(Long.valueOf(s))) answer++;
        }

        return answer;
    }

    public boolean checkPrime(long s) {
        if (s == 1) return false;

        for (int i = 2; i <= (int) Math.sqrt(s); i++) {
            if (s % i == 0) return false;
        }
        return true;
    }
}

ㅇ어차피 문제의 조건을 따르다 보면 0을 만났을 때는 소수 판별을 할 필요가 없으므로 문자열 전체를 “0”을 기준으로 잘라준다. (이렇게 하기 전에는 “0”을 만나면 continue 하는 식으로 진행했었다.)

잘라진 문자열을 checkPrime 메서드를 통해 소수인지 판별해주면 되는데, 소수 판별 역시 입력받은 값을 그대로 다 비교할 것이 아니라 다음의 규칙을 통해 루트를 씌워준 값과 비교하면 되는 것을 알 수 있다.

ex) 36

1 x 36

2 x 18

3 x 12

4 x 9

6 x 6

9 x 4

12 x 3

18 x 2

36 x 1

위에서 왼쪽을 a, 오른쪽을 b라고 할 때 a, b 중 어느 한쪽은 항상 비교대상의 루트를 씌운 값보다 작거나 같음을 알 수 있다.

이를 적용하여 소수를 판별해주고 맞다면 answer++ 해주면 끝이다.