*[프로그래머스] Lv2 k진수에서 소수 개수 구하기 / Java

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

프로그래머스

코드

import java.util.*;
class Solution {
  public int solution(int n, int k) {
        /*
        1. n 을 k 진수로 바꾼다.
            1) n을 k로 나눈 나머지가 k 보다 작을때까지, n을 k로 나누는 것을 반복
            2) 반복마다 n을 k로 나눈 나머지를 문자열 앞쪽에 붙여나간다.
        2. 문자열의 처음 문자부터 하나씩 확인한다.
            - 0인 경우
                * stack 에 담겨있는 문자들을 모두 꺼낸다.
                    * stack 이 비어있는 경우
                        * continue;
                    * 1 한개만 있는 경우
                        * stack 비운다
                        * continue;
                    * 이외의 경우
                        * 꺼낸 문자들을 문자열로 만든다.
                        * 10진수로 변환한다. Integer.parseInt();
                        * 절반까지 나눠보면서 0으로 나누어떨어지는 경우가 없으면
                          answer ++;
                        * stack 비운다.
                        * continue;
            - 이외
                * stack 에 넣는다.
        3. stack 이 비어있는 지 확인
            * 비어 있지 않다면
                * 꺼낸 문자들을 문자열로 만든다.
                * 10진수로 변환한다. Integer.parseInt();
                * 절반까지 나눠보면서 0으로 나누어떨어지는 경우가 없으면
                  answer ++;
        4. answer 반환한다.
        */

    int answer = 0;

    //1번 로직
    StringBuilder transSb = new StringBuilder();
    while(n/k>0){
      transSb.insert(0, n%k);
      n=n/k;
    }
    transSb.insert(0, n%k);

    StringBuilder tmpSb = new StringBuilder();
    Stack<Character> stack = new Stack<>();
    Boolean isPrime = true;
    //2번 로직
    for(int i=0; i<transSb.length(); i++){
      if(transSb.charAt(i)=='0'){
        if(stack.empty()) continue;
        while(!stack.empty()){
          tmpSb.insert(0,stack.pop());
        }
        if(tmpSb.length()<=1&&tmpSb.charAt(0)=='1'){
          stack.clear();
          tmpSb.delete(0,tmpSb.length());
          continue;
        }
        else{
          int num = Integer.parseInt(tmpSb.toString());
          for(int j=2; j<num/2; j++){
            if(num%j==0) isPrime = false;
          }
          if(isPrime) answer++;
          stack.clear();
          tmpSb.delete(0,tmpSb.length());
          continue;
        }

      }
      else{
        stack.push(transSb.charAt(i));

      }
    }

    while(!stack.isEmpty()) {
      tmpSb.insert(0, stack.pop());
    }
      int num = Integer.parseInt(tmpSb.toString());
      for(int j=2; j<num/2; j++){
        if(num%j==0) isPrime = false;
      }
      if(isPrime) answer++;


    System.out.println(answer);
    return answer;
  }
}

2시간 가까이 IDE의 디버거까지 활용하며 풀었지만 결과는

좀 슬프다. ㅠ 

나름대로 로직을 짜서 풀었는데,, 일반적인 이론들을 몰라서 적용하지 않는 게 문제인 거 같다.

좀 더 알고리즘의 이론을 공부해봐야겠다.

 

다른 분들의 풀이

class Solution {
    public boolean isprime(long n){
        if(n <= 1) return false;
        else if(n == 2) return true;
        for(int i = 2; i <= Math.sqrt(n); i++)
            if(n % i == 0) 
                return false;
        return true;
    }
    public String to_Knum(int n, int k) {
        String res = "";
        while(n > 0) {
            res = n % k + res;
            n /= k;
        }
        return res;
    }
    public int solution(int n, int k) {
        int answer = 0, i, j;
        String s = to_Knum(n,k);
        for(i = 0; i < s.length(); i = j) {
            for(j = i + 1; j < s.length() && s.charAt(j) != '0'; j++);
            if(isprime(Long.parseLong(s.substring(i,j))))
                answer++;
        }
        return answer;
    }
}

그냥 0을 기준으로 숫자들을 나누고 각 숫자들이 소수인 지 확인하면 된다고 한다.

일반적으로 소수구하기 주제는 '에라토스체네스의 체' 라는 이론을 사용한다고 해서 공부해봐야 겠다.

그리고 진수 변환 후 숫자가 커질 수 있어서 Long 타입으로 처리하는 방법도 볼 수 있었다.