Lv.2 : k진수에서 소수 개수 구하기

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 입력받은 정수 n을 k진수로 변환 뒤 0으로 구분해 나온 값들 중 소수의 개수를 반환한다.

🔸 문제 풀이 🔸

• 먼저 k진수 변환 및 0으로 잘라 문자열 배열을 생성한다.
• 배열의 문자 하나씩 소수인지 판별한다.

---

🔸 코드 🔸

class Solution {
    public int solution(int n, int k) {
        // 진수 변환 & 0으로 구분
        String[] ss = Integer.toString(n, k).split("0+");

        // 소수 판별
        int answer = 0;

        for (String s : ss) {
            boolean flag = true;
            Long num = Long.parseLong(s);

            if (num < 2) continue;

            int max = (int)Math.sqrt(num);
            for (int i = 2; i <= max; i++) {
                if (num % i == 0) {
                    flag = false;
                    break;
                }
            }

            if (flag) answer++;
        }

        return answer;
    }
}

🔸 코드 해석 🔸

• Integer.toString()을 통해 3~10진수 변환을 쉽게 수행할 수 있다.
• String.split()으로 문제 조건에 따라 0을 기준으로 문자열을 만드는데, 중복되는 0도 포함하기 위해 정규표현식에 '+'를 붙인다.
• 각 문자열의 소수 판별을 위해 정수로 변환 뒤, 2부터 정수의 제곱근까지 나뉘는 값이 있는지 확인한다.
  • 문자열을 정수로 변환할 때 Integer의 범위를 초과하므로 long으로 저장해야 한다.
  • 나뉘는 값이 없다면 소수이다.
• 소수의 개수를 반환한다.

---

🔸 end 🔸

• 프로그래머스 코딩테스트 연습 힌트 모음집에 포함되는 문제여서 힌트를 볼 수 있었다.
  • 소수를 판별하기위해 제곱근까지 검사한다는 것과 long으로 써야한다는 힌트였는데 기존 코드에서 둘 다 해당되었다.
  • 정수를 int로 변환하고 소수 판별은 에라토스테네스의 체를 썼었는데, long으로 바꾸고 나니 적용할 수 없어서 제곱근 방법으로 변경해야 했다.
  • 배열이 long 크기가 된다면 에라토스테네스의 체는 쓸 수 없다는걸 새롭게 배울 수 있었다.
• 생각보다 문제들이 알차고 설명이 잘 되어있어서 모음집의 문제만 따로 풀어도 좋을 것 같다.