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

k진수에서 소수 개수 구하기 : https://programmers.co.kr/learn/courses/30/lessons/92335

---

Problem

---

Solve

소수를 찾는 조건과 소수 찾는 코드만 신경써주면 되는 문제.

주어지는 정수에서 k진수로 변경했을때 소수를 찾는 조건

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

해당 조건을 봤을때 포인터로 이동하면서 0일때는 무시하고 그 외의 값이 나왔을 때는 저장해두었다가 그 뒤에 0이 나왔을 때 소수 판별을 한 후 소수라면 갯수를 카운트 해주는 식으로 하면 되겠다고 생각했다.

문제 풀이 순서는 아래와 같다.

1. 주어진 정수를 k진수로 변경
2. k진수를 배열로 받은 후 위에 설명했던 조건으로 예상 소수 값을 저장한다.
3. 0을 찾았을 땐 저장된 예상 소수 값을 소수 판별 후 소수 라면 갯수를 카운트 해준다.

문제를 풀때 조심해야하는게 두가지 있다.
첫번째는 정수를 k진수로 변경했을때 int의 최대값을 초과한다. 예를들어 3진수로 변경했을 때 그럴 가능성이 크기 때문에 long값을 써주도록 하자.

두번째는 소수를 찾는 코드에서 1번 테스트케이스가 시간초과가 발생했는데
https://programmers.co.kr/questions/25532 도움되는 설명을 보게 되었다.
내가 쓰던 방법은 시간복잡도에 좋지 못한 영향을 미치게 된다. 하나 또 알아가게 된다.

---

Code

import java.util.*;
class Solution {
    public int solution(int n, int k) {
    	//정수를 k진수 배열로
        long[] kArr = toKArr(n,k);
        
        int idx=0;
        int count=0;
        List<Integer> prime = new ArrayList<>();
        StringBuilder num = new StringBuilder();
        while(idx<kArr.length){
        	//idx가 0을 찾거나 모든 k진수를 확인할때까지 예상 소수 저장
            while(idx<kArr.length && kArr[idx]!=0){
                num.append(kArr[idx]);
                idx++;
            }
            //예상된 소수가 있다면 소수 판별후 count
            if(num.length()>0){
                if(isPrime(num.toString())) count++;
            }
            idx++;
            num = new StringBuilder();
        }
        //k진수를 끝까지 탐색했을 때 예상된 소수가 저장만 되고 판별되지 않고 남아있을수 있을수 있다.
        if(num.length()>0){
            if(isPrime(num.toString())) count++;
        }
        
        return count;
    }
    
    //소수 판별
    boolean isPrime(String num){
        long n = Long.parseLong(num);
        
        if(n==0 || n==1) return false;
        for(long i=2;i<=(long)Math.sqrt(n);i++){
            if(n%i==0) return false;
        }
        return true;
    }
    
    long[] toKArr(int n,int k){
        Stack<Integer> stack = new Stack<>();
        
        while(n>k){
            stack.push(n%k);
            n = n/k;
        }
        stack.push(n);
        
        long[] arr = new long[stack.size()];
        for(int i=0;i<arr.length;i++){
            arr[i]=stack.pop();
        }
        return arr;
    }
}

---

Result

---

Reference

https://programmers.co.kr/questions/25532