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

문제내용

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

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

 

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

---

문제 접근 방법

문제 로직 자체는 간단하게 생각하면된다.

먼저 입력받은 n을 k진수에 맞게 숫자를 바꿔주고, 바꿔준 숫자에서 0사이에 있는 모든 숫자에 대해 소수인지 아닌지를 판단해 주면된다. 이를 좀더 풀어서 설명하면 아래와 같다.

 

로직

1. k진수로 숫자바꾸기.
   n은 10진수로 이뤄진 양의 정수로 k진수로 바꾸기 위해선 n을 k로 나눈 나머지를 차례대로 이어 붙여주면된다.
   
   
2. 소수 판단하기.
   소수를 판단하는 알고리즘은 에라토네스의 체와 제곱근을 활용하는 두가지 방법이 존재한다.
   참고로 나는 제곱근을 활용하는 알고리즘을 사용했다.그리고 소수를 판단하기전 숫자를 만드는 방법은 아래와 같다.
   
   1. k진수로 바꾼 숫자를 하나씩 탐색하면서 0이 아닌숫자를 하나씩 StringBuilder 객체에 붙여준다.
   2. 첫번째 숫자( 오른쪽에 0하나 )
      -> 첫번째로 0이 나오는 순간에 StringBuilder 객체에는 첫번째로 만들어진 숫자가 만들어져 있다.
      -> 첫번째로 만들어진 숫자가 소수인지 아닌지 판단한다.
      -> 소수이면 answer 변수에 1을 더해주고 아니면 0을 더해준다.
   3. 가운데 숫자( 양쪽에 0하나씩 )
      -> 2번에서 첫번째 0이후에 0이 한번 더 나왔을때가 0과0사이에 있는 숫자가 만들어지는 순간이다.
      -> 이때 숫자가 만들어지면 소수인지 판단하고 answer 증가 여부를 결정한다.
      -> k진수로 바꾼숫자를 전부 탐색할때까지 3번을 반복한다.
   4. 마지막 숫자( 왼쪽에 0하나 )
      -> 반복문이 끝났을때 마지막으로 만들어져있는 숫자가 있는지 없는지 보고 있다면 소수인지 아닌지 판단해준다.

전체적인 로직은 위와같고 자세한 내용은 코드를 보자.

---

풀이

public class Solution {
	static int answer = 0;

	public static int solution(int n, int k) {
		String num = "";//진법 바꾸고나서 숫자
		
		if(k!=10) num = transNum(n,k);//10진법이 아닐때 k진수로 바꿔주고
		else num = String.valueOf(n);//10진접일땐 그대로 num에 넣어주기
		
		//숫자 잘라서 소수 판단하기
		isPrime(num);

		return answer;
	}
	
	//숫자 변환
	public static String transNum(int n, int k) {
		StringBuilder sb = new StringBuilder();//바뀔수
		int mock = n; //몫
		int mod = 0; //나머지
		
		//몫이 0이 될때까지 반복
		while(mock!=0) {
			mod = mock % k;
			mock = mock / k;
			
			//나머지를 가장앞에 넣기
			sb.insert(0, mod);
		}
		
		return sb.toString();
	}
	
	public static void isPrime(String num) {
		StringBuilder sb = new StringBuilder();
		boolean first = false; //첫번째 숫자 확인용도
		
		//zero가 true가 될때 이전에 현재 나온 0과 이전에 나왔던 0 사이의 숫자를
		//소수판단하기 위한 변수
		boolean zero = false; 
		
		for(int i=0; i<num.length(); i++) {
			if(num.charAt(i)!='0') sb.append(num.charAt(i)); //0이 아닐때 추가 
			
			//첫번째 0일경우 즉, 처음으로 만들어지는 숫자를 의미(오른쪽에 0하나)
			if(num.charAt(i)=='0' && !first) {
				answer += prime(sb.toString());//소수 판단
				first = true;
				sb.setLength(0);//초기화
			}
			//첫번째와 마지막으로 만들어지는 숫자를 제외하고 중간에 나오는 숫자(양옆에 0하나씩)
			else if(num.charAt(i)=='0' && first) {
				zero = true;
				if(zero && sb.length()>0) { //숫자가 만들어졌을때
					answer += prime(sb.toString());//소수 판단
					sb.setLength(0);//초기화
					zero = false;	
				}else if(zero && sb.length()==0) { //숫자가 안만들어졌을때
					zero = false;
				}
			}
			
		}
		
		//마지막 숫자 만들어졌을때(왼쪽에 0하나)
		if(sb.length()>0) answer += prime(sb.toString());
	}
	
	public static int prime(String n) {
		double num = Double.parseDouble(n);
		
		if(num <= 1) return 0;//1은 소수가 아님
		if(num <= 3) return 1;//2,3은 소수임
		if(num % 2 == 0) return 0;//2로 나눠지는 짝수는 소수가 아님
		
		//홀수만 선택하여 루트num까지 탐색
		for(int i=3; i<=Math.sqrt(num); i+=2) {
			if(num%i == 0) return 0;//나눠떨어지면 소수가 아님(1과 본인제외 다른 약수가 있다는 뜻)
		}
		
		//그외에는 소수임
		return 1;
	}
}

---

마치며

10진수에서 진수를 바꾸는 방법과 소수를 판단해주는 알고리즘을 공부해 볼 수 있었다.

위에서 나온 제곱근을 활용한 소수 판단 알고리즘의 시간복잡도는 O(n^(1/2))라는 것을 알아두자.

또한 에라토스테네스의 체 라는 알고리즘도 공부해보면 좋을듯하다.