문제

프로그래머스 lv2 - k진수에서 소수 개수 구하기

풀이

모든 소수 조건이 0이 포함되어 있기 때문 문자열을 "0"을 기준으로 나누면 된다.
-> 주의 사항으로 "110011"인 경우 나누면 11,'',11이 되므로 나눌 때 정규표현식을 사용하여 0{1,}로 나눠야 한다.

내가 놓친 부분
처음 풀었을 때 테케 1, 11번 런타임 에러 발생했다.
-> n의 최대가 100만이라서 n진법 변환시 string 길이가 int 범위를 넘어가는 경우가 생겨서 발생한 문제

그래서 k진법으로 변환된 string을 long type으로 바꿔줘야 한다.

그 후 11번 테케는 통과했지만 1번 테케는 여전히 시간초과 발생했다.
-> 변환한 long 타입 숫자(num)가 매우 큰 경우가 있기 때문에 아래 for문을 돌면 시간초과가 발생한다.

for (long i = 2; i <= num; i++)
   if (num % i == 0) 
      return false;

소수 판별은 해당 수의 제곱근까지만 체크하면 그 다음부터는 중복이므로 Math.sqrt()를 사용한다.

for (long i = 2; i <= Math.sqrt(num); i++)
    if (num % i == 0) 
       return false;

어려웠던 점

처음에 멍때린 문제이다. 어떻게 풀어야 하는거지? 싶었다.
"0"을 기준으로 문자열을 나누는 것을 생각해내는데 시간이 오래 걸렸다.

코드

import java.util.*;
class Solution {
    boolean check(long num) {
        if (num == 1) return false;
        if (num == 2) return true;
        for (int i = 2; i <= Math.sqrt(num); i++)
            if (num % i == 0)
                return false;
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        String str = "";
        while (n > 0) {
            str = String.valueOf(n % k) + str;
            n /= k;
        }
        String[] list = str.split("0{1,}");
        for (String s : list) {
            if (check(Long.parseLong(s)))
                answer++;
        }
        return answer;
    }
}

저작자표시