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

작성일: 2024-11-12

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92335

접근 방식

먼저 주어진 숫자를 K진수로 변환한다.

이후, 세 가지 방식을 통해 소수 여부를 판별한다.

첫째, 문자열을 세 개씩 끊어서 0P0 이 되는지 확인.
둘째, P0 처럼 0이 나오기전까지 있는 진행되는 숫자 P가 소수인지 확인. 셋째, 0P 처럼 앞에 0이 있고 뒤에 숫자 P가 소수인지 확인.

P처럼 소수 양쪽에 아무것도 없는 경우는 둘째

잘못된 접근

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String target = Integer.toString(n, k);
        OPO
        for(int i=0; i<target.length()-2; i++){
            String tmp = target.substring(i, i+3);
            if(tmp.charAt(0)=='0' && tmp.charAt(2)=='0' && isPrime(tmp.charAt(1)-'0')){
                answer++;
            }
        }
        if(target.replaceAll("0", "").length()==target.length()){
            if(isPrime(Long.parseLong(target))) answer++;
            return answer;
        }
        String tmp = "";
        for(int i=0; i<target.length(); i++){
            if(target.charAt(i)!='0') tmp+=target.charAt(i);
            else break;
        }
        if(tmp.length()>0 && isPrime(Long.parseLong(tmp))) answer++;
        tmp="";
        for(int i=target.length()-1; i>=0; i--){
            if(target.charAt(i)!='0') tmp+=target.charAt(i);
            else break;
        }
        if(tmp.length()>0 && isPrime(Long.parseLong(tmp))) answer++;
        return answer;
    }

    boolean isPrime(long number){
        if(number==1L) return false;
        for(long i=2; i<number; i++){
            if(number%i==0) return false;
        }
        return true;
    }
}

문제가 발생했다. 분명히 로직은 맞는 것 같은데 정답은 아니다.

곰곰히 생각해보다 아주 중요한 포인트를 발견했다!!!

바로 세 자리로 제한을 둔 것 ㅋㅋ. 세 자리가 아니라 0과 0사이의 숫자를 판별해야 한다.

이런

잘 된 접근

이런 저런 방법을 생각하다 중요한 점을 발견했다.

바로, 0을 기준으로 분리하는 것.

어차피 왼쪽에 0이 있던, 오른쪽에 0이 있던 좌우에 0이 있던

0으로 모든 것을 나누면 해결 된다.

실제로 주어진 에시도

2 1 1 0 2 0 1 0 1 0 1 1인데, 이것도 0으로 분리하면
211 ,2, 1, 1, 11 이렇게 된다. 여기서 어차피 1은 소수가 아니기 때문에 제외하면
211, 2, 11 이 되고 이 세 수는 모두 소수이다.

주어진 다른 수도 판별해보자.
1 1 0 0 1 1인데, 이것도 0으로 분리해보자.
11, 11이 된다. 이 두 수 또한, 소수이다.

결과

소스 코드

import java.util.*;
class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String target = Integer.toString(n, k);
        String arr[] = target.split("0");
        for(String a:arr){
            if(!a.equals("")){
                if(isPrime(Long.parseLong(a))) answer++;
            }
        }
        return answer;
    }

    boolean isPrime(long number){
        if(number==1L) return false;
        for(long i=2; i<=Math.sqrt(number); i++){
            if(number%i==0) return false;
        }
        return true;
    }
}

완성 코드이다.

먼저 split을 통해 소수여부 판단을 위한 배열을 생성한다.

이후, 빈칸이 아닌 경우에 한해서 소수 판별이후 answer++를 한다.

여기서 소수 판별의 경우, 제곱근까지만 판별을 하면 된다.
(어차피 대칭적으로 제곱근을 기준으로 약수가 이루어지기 때문에, 모든 수를 판별할 필요X)

다른 접근 방식

없음.

느낀 점

항상 문제를 풀 때마다 느끼지만, 무작정 무식하게 풀지말고 해결 과정에서의 패턴을 찾아보자고 노력하지만 잘 안되는 것 같다

문제를 많이 풀어보는 수 밖에