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

문제 링크

k진수에서 소수 개수 구하기

풀이

• 문제를 몇 단계 나눠서 풀었더니 의외로 쉽게 풀렸다.
• k 진수로 변환 , 판단이 필요한 숫자 분별, 소수 확인
• 정답률이 높은걸로 정렬하고 풀었더니 잘 풀려서 기분은 좋다.
• 추가로 소수인지 판별하는 방법중에 에러토스테네스의 체 라는 알고리즘이 있던데 관련해서 추가로 공부해봐야겠다.

import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;
import java.util.stream.Collectors;

class Solution {
	public int solution(int n, int k){
		Deque<Integer> deque = new LinkedList<>();
		// k 진수로 변경
		while (n != 0){
			deque.push(n % k);
			n = n / k;
		}

		String chanegedNumber = deque.stream().map(Objects::toString).collect(Collectors.joining());

		// 변경된 수에서 소수 찾기
		String[] split = chanegedNumber.split("0");
		int result = 0;
		for(String s : split){
            // 소수 판별
			if(s.length() > 0 && !s.equals("1") && isPrime(Long.parseLong(s))){
				result+=1;
			}
		}

		return result;
	}

	private boolean isPrime(long n){
		for(int i = 2; i <= (long) Math.sqrt(n); i++){
			if(n % i == 0){
				return false;
			}
		}
		return true;
	}
}