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

문제 설명

 

 

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

풀이 : Success

소스 코드

import java.util.HashSet;
import java.util.List;
import java.util.stream.IntStream;

class Solution {
    public int solution(int n, int k) {
        StringBuilder sb = new StringBuilder();
        String base = "0123456789";

        while (n / k != 0) {
            sb.append(base.charAt(n % k));
            n /= k;
        }
        sb.append(base.charAt(n % k)).reverse();
        String[] nums = sb.toString().split("0");

        int result = 0;
        for (String num : nums) {
            if (num.isEmpty()) continue;
            if (isPrime(Long.parseLong(num))) {
                result++;
            }
        }

        return result;
    }

    public boolean isPrime(long num) {
        HashSet factors = IntStream.rangeClosed(1, (int) Math.sqrt(num))
                .filter(i -> num % i == 0)
                .mapToObj(i -> List.of(i, num / i))
                .collect(HashSet::new, HashSet::addAll, HashSet::addAll);

        return num > 1 && factors.size() == 2 && factors.contains(1) && factors.contains(num) ? true : false;
    }
}

 

풀이 회고

우선 이 문제를 풀기 위해서는 주어진 양의 정수 n을 k진수로 변환시켜주었어야 했습니다. 이때 k는 3~10으로 최대 10진수이므로 필요한 수는 0~9에 해당하므로 이를 활용하기 위해 String 변수 base에 "0123456789"를 저장시켜주도록 했고 while문을 통해 k 진수의 수를 구했습니다.(k진수 구할 때 reverse 뒤집기 유념)

문제에서 요구하는 조건들을 살펴보면 결국 주어진 k진수에서 "0을 구분으로 존재하는" 수 중 소수의 개수를 구하는 것입니다. 이를 위해 split를 통해 "0"으로 구분시켜 각각의 수들을 얻어냈고 각각의 수별로 소수인지 판별하도록 했습니다.

해당 수가 소수인지 판별할 때 일반적인 for문이나 while문을 통해서 구하면 시간복잡도 성능이 안좋아집니다. 저는 시간복잡도 성능을 개선하기 위해서 해당 수의 인자(약수)를 구한 후 이를 HashSet에 저장시키도록 했고(중복 방지) 소수의 조건인 1과 자기 자신의 수로만 떨어지는지 체크함으로써 해당 수가 소수인지를 판별했습니다.

최종적으로 소수로 판별될 때마다 result 값에 1씩 더해주어 결과값을 구할 수 있었습니다.

 

 

참고자료

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