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

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

class Solution {
	String change(int num, int base) {
		int quotient = num / base;
		int mod = num % base;
		if (quotient != 0) {
			return change(quotient, base) + String.valueOf(mod);
		} else {
			return String.valueOf(mod);
		}
	}

	boolean check(long num) {
		if (num == 2)
			return true;
		if (num == 1 || num % 2 == 0)
			return false;
		// 루트값 까지만 나눠보기
		for (int i = 3; i <= Math.sqrt(num); i++) {
			if (num % i == 0)
				return false;
		}
		return true;
	}

	public int solution(int n, int k) {
		// 1. 진법 변환(몫이 0이 될때까지 나누기 -> 나머지를 역순으로)
		String number = change(n, k);
		// 2. 0으로 구분해서 소수인지 확인
		String[] nums = number.split("0+");
		int answer = 0;
		for (String num : nums) {
        // 문자열 처음에 구분자가 나올 경우 split 메서드에 의해 공백 문자 발생
			if (!num.equals("") && check(Long.valueOf(num))) {
				answer++;
			}
		}
		return answer;

	}

}

• 풀이 과정
  • 진법 변환 : change 메서드
    • 몫이 0이 될때까지 나누고, 나머지들을 String으로 붙임
      ex) 13을 8진수 변환
      -> 13 / 8 = 1 || 5
      -> 1 / 8 = 0 || 1
      => "15"(8)
  • 소수 판별 : 에라토스테네스의체 이용(루트값까지)
    • 진법으로 변환한 수로, 100만보다 더 커진 숫자인 경우가 있는듯
      • long으로 해야 런타임오류 발생x
    • 2를 제외한 짝수는 모두 소수가 아니니깐, 3부터 검사하면서 2씩 증가하면 반복 횟수를 조금 줄일 수 있음

• spilt 메서드 주의할 점
  • 문자열의 시작과 끝에 구분자 나올 경우 공백 문자열 추가됨
    • ex) split("0ab0", "0") -> ["", "ab", ""]
    • 하지만 split 메서드의 경우 맨 마지막 공백은 제거됨 -> ["", "ab"]
  • 연속된 문자열 발생 시 구분 문자열 사이 공백 추가
    • ex) split("ab0000c", "0") -> ["ab", "", "", "", "c"]
    • 정규표현식으로 예방 가능
      • ex) split("ab000c", "0+") -> ["ab", "c"]

   public class ClassNameHere {
   public static void main(String[] args) {
      String s = "0abc0";
      String[] sArr = s.split("0");
      
      for(String c : sArr) {
         if(c.equals(""))
            System.out.print("난 공백!");
         else{
         System.out.println(c);
         }
      }
   }
}

출력결과

• split 메서드 별도 설정 없는 한 맨 마지막 공백 제거됨을 확인

• 출처 1 : 카카오 코딩 테스트 - k진수에서 소수 개수 구하기 (Java 풀이)
• split 관련 출처 : 뤼튼