[프로그래머스] Lv.2 k진수에서 소수 개수 구하기 문제 해결 과정

 문제 링크

---

 https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

 

 

 해결 과정

---

 문제를 보고 느꼈던 점은 소수를 어디까지 구해야 할지 가장 의문이 들었습니다. 그래서 모든 경우에서 계산 후 가장 큰 값을 출력해 봤습니다. 처음에 int형 내에서 다 표현할 수 있을 줄 알고 int형으로 하다 NumberFormatException 뜨는 것을 확인하고 바로 long으로 바꿨습니다.

private long getMax() {
    long max = -1;
    for(int i = 1; i <= 1000000; i++) {
        for(int d = 3; d <= 10; d++) {
            String[] split = Integer.toString(i, d).split("0");
            for(String s : split) {
                if(!s.isEmpty()) {
                    max = Math.max(max, Long.parseLong(s));
                }
            }
        }
    }
    return max;
}

출력 결과

 

 그래서 "이 숫자까지 미리 소수를 구해야 하나?"라는 생각을 하다가, 예전에 소수 관련 문제 풀 때 소수 판별 알고리즘을 사용한 게 생각나서 미리 소수를 구하지 않고, 판별 여부만 확인했더니 빠르게 해결됐습니다.

 

 

채점 결과

 

 

 

 

 전체 코드

---

class Solution {
    public int solution(int n, int k) {
        int answer = -1;
        //주어진 숫자를 k진수로 변형
        String[] numbers = Integer.toString(n, k).split("0");
        answer = getPrimeNumbers(numbers);
        return answer;
    }
    
    private int getPrimeNumbers(String[] numbers) {
        long max = -1;
        int count = 0;
        for(String number : numbers) {
            if(number.isEmpty() || number.equals("1"))
                continue;
            
            count++;
            long num = Long.parseLong(number);
            //해당 숫자가 소수인지 아닌 지 검사
            //만약 소수가 아니면 전에 미리 추가했던 count값을 감소시킨 후 반복문 탈출.
            for(long l = 2; l <= Math.sqrt(num); l++) {
                if(num % l == 0) {
                    count--;
                    break;
                }
            }
        }
        return count;
    }
}

 

 

 

 정리

---

• 어떤 숫자를 k진수로 표현할 때는 <Wrapper.class>.toString(number, k) 메서드를 사용하자
  (Integer.toString, Long.toString() 등등..)
• 소수 판별 알고리즘 까먹지 말자!