프로그래머스 - k진수에서 소수 개수 구하기 :: 2022 KAKAO BLIND RECRUITMENT

---

문제

코딩테스트 연습 - k진수에서 소수 개수 구하기 | 프로그래머스 스쿨 (programmers.co.kr)

---

풀이

문제가 복잡해 보이지만 간단히 해결할 수 있는 문제입니다.

문제의 핵심은 0P0, 0P, P0 해당 규칙에 포함되며 소수인 개수를 구해야 합니다.

0P0, 0P, P0 의 규칙은 0으로 Split 하면 쉽게 구할 수 있습니다.

지문의 예처럼 211020101011 을 0으로 Split하면 [ "211", "2", "1", "1", "11" ] 을 구할 수 있습니다.

해당 배열들이 소수인지 아닌지만 판별하면 됩니다.

코드1

class Solution {
    public int solution(int n, int k) {
        String n_to_k = changeNotation(n, k);

        int count = 0;
        String[] splitZero = n_to_k.split("0");
        for(String str : splitZero) {
            if(!str.trim().isEmpty()) {
                long num = Long.parseLong(str);
                if (isPrime(num)) count++;
            }
        }

        return count;
    }

    public String changeNotation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            sb.insert(0, n % k);
            n /= k;
        }

        return sb.toString();
    }

    public boolean isPrime(long num) {
        boolean isPrime = true;
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                isPrime = false;
                break;
            }
        }
        return num <= 1 ? false : isPrime;
    }
}

• 진법 변환 changeNotation
  진법 변환하는 알고리즘은 이전 글을 참고해 주세요.
  프로그래머스 - 3진법 뒤집기 java :: 월간 코드 챌린지 시즌1

  
  

• 소수 판별 isPrime
  소수 판별 알고리즘은 이전 글을 참고해 주세요.
  프로그래머스 - 소수 만들기 java :: Summer/Winter Coding(~2018)

  
  

• 0P, 0P0, P0 규칙
  

  

  
  

• 정확성 테스트

  테스트	결과 (시간)
  테스트 1 〉	통과 (14.55ms, 83.5MB)
  테스트 2 〉	통과 (0.17ms, 79MB)
  테스트 3 〉	통과 (0.22ms, 69.9MB)
  테스트 4 〉	통과 (0.20ms, 86.6MB)
  테스트 5 〉	통과 (0.29ms, 75.2MB)
  테스트 6 〉	통과 (0.17ms, 72.7MB)
  테스트 7 〉	통과 (0.24ms, 73.2MB)
  테스트 8 〉	통과 (0.16ms, 71.4MB)
  테스트 9 〉	통과 (0.15ms, 81.1MB)
  테스트 10 〉	통과 (0.16ms, 77.9MB)
  테스트 11 〉	통과 (0.18ms, 69.6MB)
  테스트 12 〉	통과 (0.27ms, 84.9MB)
  테스트 13 〉	통과 (0.16ms, 78.5MB)
  테스트 14 〉	통과 (0.11ms, 78.8MB)
  테스트 15 〉	통과 (0.09ms, 75MB)
  테스트 16 〉	통과 (0.14ms, 78.3MB)

코드2

class Solution {
    public int solution(int n, int k) {
        int count = 0;
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            int ins = n % k;
            if(ins != 0) {
                sb.insert(0, n % k);
            } else {
                if(sb.length() > 0) {
                    long num = Long.parseLong(sb.toString());
                    if (isPrime(num)) count++;
                }
                sb.setLength(0);
            }
            n /= k;
        }
        if(sb.length() > 0) {
            long num = Long.parseLong(sb.toString());
            if (isPrime(num)) count++;
        }

        return count;
    }

    public boolean isPrime(long num) {
        boolean isPrime = true;
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                isPrime = false;
                break;
            }
        }
        return num <= 1 ? false : isPrime;
    }
}

Split을 사용하지 않은 방법입니다.

진법 변환을 하면서 "0"이 나올 때마다 이전까지 구했던 수가 소수인지 즉시 판별하는 방법입니다.

1번 코드보다 쪼~끔 빨라졌네요

• 정확성 테스트

  테스트	결과 (시간)
  테스트 1 〉	통과 (10.74ms, 79.7MB)
  테스트 2 〉	통과 (0.09ms, 76.4MB)
  테스트 3 〉	통과 (0.09ms, 81.2MB)
  테스트 4 〉	통과 (0.10ms, 76.9MB)
  테스트 5 〉	통과 (0.10ms, 72.6MB)
  테스트 6 〉	통과 (0.10ms, 72.8MB)
  테스트 7 〉	통과 (0.10ms, 75MB)
  테스트 8 〉	통과 (0.14ms, 82MB)
  테스트 9 〉	통과 (0.10ms, 75.9MB)
  테스트 10 〉	통과 (0.15ms, 75.6MB)
  테스트 11 〉	통과 (0.09ms, 74.1MB)
  테스트 12 〉	통과 (0.08ms, 77.1MB)
  테스트 13 〉	통과 (0.13ms, 75.3MB)
  테스트 14 〉	통과 (0.12ms, 78.1MB)
  테스트 15 〉	통과 (0.10ms, 78.7MB)
  테스트 16 〉	통과 (0.16ms, 77.3MB)

---