[프로그래머스] k진수에서 소수 개수 구하기 (Java/자바)

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

프로그래머스

풀이 방법

프로그래머스의 124 나라의 숫자 를 풀 때의 방법으로 k진수로 바꾸어주었다.

[프로그래머스] 124 나라의 숫자 (Java/자바)

 

예제 테케는 맞았는데 채점을 해보니 1번 테스트 케이스에서 런타임 에러가 발생해서 질문을 찾아보았다.

P가 int 범위를 넘어가는 경우도 있기 때문에 temp를 Long으로 변환시켜 주었다.

또한 소수인지 확인할 때에도 O(N)이 걸릴 경우 시간 초과가 발생해서 O(√𝑁)의 방법으로 해결해야 한다.

 

package Programmers;

class Solution_k진수에서소수개수구하기 {
	public int solution(int n, int k) {
		int answer = 0;

		// k진수 변환
		String changed = "";
		if (k == 10) {
			changed = Integer.toString(n);
		} else {
			while (n > 0) {
				int remain = n % k;
				n /= k;
				changed = remain + changed;
			}
		}

		// 조건에 맞는 소수 구하기
		int len = changed.length();
		String temp = "";
		for (int i = 0; i < len; i++) {
			temp = "";
			while (i < len && changed.charAt(i) != '0') {
				temp += changed.charAt(i++);
			}
			if (temp != "" && isPrime(Long.parseLong(temp))) {
				answer++;
			}
		}

		return answer;
	}

	/**
	 * num이 소수면 true 반환
	 */
	public boolean isPrime(long num) {
		if (num == 1) {
			return false;
		}

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

		return true;
	}
}