Programmers Lv2 k 진수에서 소수 개수 구하기 (JAVA)

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가 될 수 없습니다.

---

풀이

나의 부족함을 많이 느낀 문제였다. 혼자 해보다 다른 블로그를 참고하여 풀었다.

https://devdange.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-k%EC%A7%84%EC%88%98%EC%97%90%EC%84%9C-%EC%86%8C%EC%88%98-%EA%B0%9C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-for-JAVA

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

흐름은 다음과 같다.

1. 문제에서 주어진 진수대로 정수를 변환한다.

2. 변환된 수에서 0P0, 0P, P0, P 의 경우가 있는지 탐색한다.

3. 소수판별식.

 

---

1. 주어진 진수로 정수를 변환

StringBuilder sb = new StringBuilder();
        //진수 변환
        while (n>=k){
            sb.insert(0, n%k);
            n = n/k;
        }
        sb.insert(0, n);

StringBuilder을 활용하여 나머지 값을 추가하는 형태로 작성하였다.

(3~10)진수 중 어떤 진수로 변환을 하던,

해당하는 진수보다 주어진 수가 작아질때까지의 나눈 나머지를 붙여주면 된다.

 

---

2. 탐색

String change = sb.toString(); //진수변환이 완료된 String
        
        long tmp = 0L; //P의값을 넣을 tmp 변수

        //탐색
        for(int i=0;i<change.length();i++){
            if(change.charAt(i) == '0'){
                if(tmp != 0L && is_prime(tmp)){
                    answer++;
                }
                tmp = 0L; //tmp값 초기화
            }
            else{
                tmp = tmp*10 + (change.charAt(i)-'0'); //tmp값 더해주기
            }
        }

        //마지막 tmp가 0P였을 경우 탐색
        if(tmp%10 != 0L && is_prime(tmp)){
            answer++;
        }

진수변환이 완료된 String change를 하나씩 비교한다.

만약 change에서 0이 출력되었다면,

그전에 tmp에 저장된 값이 있었는지 확인하고, tmp의 값이 소수인지 확인한다.

0이 아니라면 tmp에 값을 차곡차곡 쌓아준다.

 

change의 마지막이 0P의 경우였을 경우, 위의 for문에서 탐색하지 못하기 때문에

마지막에 if문을 사용하여 한번 더 탐색해준다.

---

3. 소수판별식

소수에 관련된 문제가 나오면, 에라토스테네스의 체를 기억해야 한다.

" k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다"

 

//소수 판별
    private static boolean is_prime(long num){
        if(num == 1){
            return false;
        }
        int max = (int)Math.sqrt(num);
        for(int i=2;i<=max;i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }

1일 경우 false를 return하고,

나머지의 경우 제곱근형태로 만들어(계산처리 시간을 줄이기 위해),

나눠지는 수가 있는지 검사해서 있으면 false 없다면 true를 반환한다.

---

전체 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
    public static int solution(int n, int k) {
       
        int answer = 0; //조건을 만족하는 소수의 개수

        StringBuilder sb = new StringBuilder();
        //진수 변환
        while (n>=k){
            sb.insert(0, n%k);
            n = n/k;
        }
        sb.insert(0, n);

        String change = sb.toString(); //진수변환이 완료된 String
        
        long tmp = 0L; //P의값을 넣을 tmp 변수

        //탐색
        for(int i=0;i<change.length();i++){
            if(change.charAt(i) == '0'){
                if(tmp != 0L && is_prime(tmp)){
                    answer++;
                }
                tmp = 0L; //tmp값 초기화
            }
            else{
                tmp = tmp*10 + (change.charAt(i)-'0'); //tmp값 더해주기
            }
        }

        //마지막 tmp가 0P였을 경우 탐색
        if(tmp%10 != 0L && is_prime(tmp)){
            answer++;
        }

        return answer;
    }

    //소수 판별
    private static boolean is_prime(long num){
        if(num == 1){
            return false;
        }
        int max = (int)Math.sqrt(num);
        for(int i=2;i<=max;i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        int S = solution(n,k);
        System.out.println(S);
    }
}

아직 부족하고 배울것이 많다는 점을 알려준 문제였다.

사실 문제가 잘 풀리지 않으면 좌절할때가 많다.

하지만 위처럼 많은 블로그의 도움을 받아 배울 수 있다는 점이 감사하다.

배고프다! 점심먹으러 가겠다!