구현 (진수 변환)

프로그래머스 2022 KAKAO BLIND RECRUITMENT Level 2 문제 k진수에서 소수 개수 구하기를 Java를 이용해 풀어보았다.
진수 변환이 포인트인 간단한 문제였다.

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/92335

---

진수 변환하기

진수 변환은 나머지 값을 계속 붙여가며 만드는 간단한 로직으로 해결 가능하다. 코드로 살펴보자.

String transform(int n, int k) {
        String s = "";
        while (n != 0) {
            int remainder = n % k;
            s = remainder + s;
            n /= k;
        }
        return s;
    }

그럼 이렇게 나온 변환된 진수를 0을 기준으로 잘라준 후에 나온 덩어리들 중 소수가 몇 개인지 카운트해주면 된다.

---

0 구분자로 잘라주기

split() 메소드를 이용해서 잘라준 후에, 0이 여러 개 반복해서 나온 경우에는 빈 문자열이 추가될 것이므로 그냥 ""이 나오면 continue;로 넘기면 된다.
코드로 살펴보자.

int answer = 0;
String s = transform(n, k);
String[] nums = s.split("0");
for (String num : nums) {
      if (num.equals("")) continue;
      if(isPrime(Long.parseLong(num)))    answer++;
}

잘려 나온 녀석이 소수일 때마다 1씩 증가시켜주면 된다.

---

isPrime(Long n) 자료형!!

처음에는 isPrime(int n)으로 했다가 테스트 케이스 1번과 11번을 통과하지 못했다. 시간 초과가 아닌 런타임 에러인 것을 봤을 때 자료형이 문제였음을 알 수 있었다. 특정 진수로 바꿨을 때 숫자가 졸라 길어질 수 있기 때문에 int가 아닌 long으로 처리해줬어야 하는 것이다.

소수 판별 로직은 자기 자신에 제곱근 때린 것까지 확인해서 한 번이라도 나누어 떨어지면 false 반환하면 된다.
코드는 다음과 같다.

static Boolean isPrime(Long num) {
        if(num==1)  return false; // 1이면 바로 넘기고
        Long end = (long) Math.sqrt(num);
        for (long i = 2; i <= end; i++)
            if (num % i == 0)
                return false;
        return true;
    }

위의 코드를 모두 합치면 다음과 같다. 내가 제출한 코드다.

import java.io.*;

public class PrimeNumber {
    static int solution(int n, int k) {
        int answer = 0;
        String s = transform(n, k);
        String[] nums = s.split("0");
        for (String num : nums) {
            if (num.equals("")) continue;
            if(isPrime(Long.parseLong(num)))    answer++;
        }

        return answer;
    }

    static String transform(int n, int k) {
        String s = "";
        while (n != 0) {
            int remainder = n % k;
            s = remainder + s;
            n /= k;
        }
        return s;
    }

    static Boolean isPrime(Long num) {
        if(num==1)  return false;
        Long end = (long) Math.sqrt(num);
        for (long i = 2; i <= end; i++)
            if (num % i == 0)
                return false;
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = 437674;
        int k = 3;
        int result = solution(n, k);
        bfw.write(result + "");
        bfw.close();
    }
}

오늘 배운 것

런타임 에러가 뜰 때는 자료형부터 의심해보자!