코딩테스트 - 프로그래머스/JAVA

[프로그래머스 / 2022 KAKAO BLIND RECRUITMENT / 자바(JAVA)] k진수에서 소수 개수 구하기

읁; 2024. 5. 17. 19:41

[프로그래머스 / 2022 KAKAO BLIND RECRUITMENT / 자바(JAVA)] k진수에서 소수 개수 구하기

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

[ 요약 ]

더보기

시작 시간 : 17시 30분

종료 시간 : 18시 18분

소요 시간(분) : 48분

 

도전 횟수 (제출 횟수) : 3

로직 및 풀이 참고 여부 : O

 

[ 풀어보기 ]

 

정답 풀이

 

📌 로직

< 메인 로직 >

  1. n을 k진법으로 변환한 String intToString을 구해준다.
    • Integer.toString(n, k)를 통해, 10진법인 n을 k진법으로 변환할 수 있다.
    • 반대로, k진법인 String num을 10진법으로 바꾸기 위해서는 Integer.parseInt(num, k)를 해주면 됨
  2. 이를 char Array로 변환한다.
    • intToString.toCharArray() 를 통해 String을 char 배열로 변환한다.
  3. StringBuffer 객체 sb를 만든다.
  4. "2"번에서 만든 charArray를 순회하는 확장 for문을 만든다. 각 요소는 char a로 받는다.
    • StringBuffer에 a를 차례로 append 해준다.
    • 이 때, a가 0이면 append 하지 않고, StringBuffer에 지금까지 쌓여 만들어진 숫자를
      소수인지 판별한다.
      • 만약 소수라면 answer ++;
      • 그리고 소수인지 아닌지와 상관없이, StringBuffer를 비워준다.

< 소수 판별 로직 >

  1. 소수인지 아닌지 판별할 숫자 num의 제곱근 n을 구한다.
  2. num을 2부터 n까지 나누었을 때,
    • 나눠 떨어지는 숫자가 있다면 이는 소수가 아니다.
    • 나눠 떨어지는 숫자가 없다면 소수이다.

📌 코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String intToString = Integer.toString(n, k); // n진법으로 바꾸기
        char[] intArray = intToString.toCharArray(); // char 배열로 변환하기
        
        StringBuffer sb = new StringBuffer(); // StringBuffer 객체 생성
        
        for(char a : intArray) {
            
            if(a == '0') { // 만약 a가 0이면
                if(sb.length()!= 0 && isPrime(sb.toString()))
                    answer++;
                sb.setLength(0); // StringBuffer 비워주기
            } else { // a가 0이 아니면
                sb.append(a);
            }
        }
        
        // for문의 순회가 끝난 후, StringBuffer가 비워지지 않았다면
        // 여기 남은 숫자들 또한 소수 판별을 해주어야 한다.
        if(sb.length() != 0 && isPrime(sb.toString()))
            answer++;
        
        return answer;
    }
    
    // 해당 숫자가 소수인지, 아닌지 판별하는 메소드
    private boolean isPrime(String n) {
        
        long number = Long.parseLong(n);
        // int -> long으로 바꾸어 런타임오류 해결
        
        if(number < 2) return false;
        
        long sqrt = (long)Math.sqrt(number);
        
        for(int i=2; i<=sqrt; i++) {
            if(number % i == 0) return false;
        }
        
        return true;
    }
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (16.06ms, 85.5MB)
테스트 2 〉	통과 (0.21ms, 76.3MB)
테스트 3 〉	통과 (0.19ms, 71.3MB)
테스트 4 〉	통과 (0.21ms, 78.3MB)
테스트 5 〉	통과 (0.20ms, 75.9MB)
테스트 6 〉	통과 (0.28ms, 77.6MB)
테스트 7 〉	통과 (0.16ms, 72.5MB)
테스트 8 〉	통과 (0.16ms, 70.2MB)
테스트 9 〉	통과 (0.16ms, 77.8MB)
테스트 10 〉	통과 (0.20ms, 75.6MB)
테스트 11 〉	통과 (0.18ms, 73.9MB)
테스트 12 〉	통과 (0.19ms, 74.6MB)
테스트 13 〉	통과 (0.23ms, 71.3MB)
테스트 14 〉	통과 (0.17ms, 70.9MB)
테스트 15 〉	통과 (0.17ms, 76.7MB)
테스트 16 〉	통과 (0.12ms, 76.7MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 


 

오답 풀이 1

📌 코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // n진법으로 바꾸기
        String intToString = Integer.toString(n, k);
        char[] intArray = intToString.toCharArray();
        
        StringBuffer sb = new StringBuffer();
        
        for(char a : intArray) {
            
            if(a == '0') {
                if(sb.length()!= 0) {
                    if(isPrime(sb.toString())) answer++;
                }
                sb.setLength(0);
            } else {
                sb.append(a);
            }
        }
        
        if(sb.length() != 0) {
            if(isPrime(sb.toString())) answer++;
        }
        
        return answer;
    }
    
    // 해당 숫자가 소수인지, 아닌지 판별하는 메소드
    private boolean isPrime(String n) {
        
        int number = Integer.parseInt(n);
        
        if(number < 2) return false;
        if(number == 2) return true;
        
        int sqrt = (int)Math.sqrt(number);
        
        for(int i=2; i<sqrt; i++) {
            if(number % i == 0) return false;
        }
        
        return true;
    }
    
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	실패 (런타임 에러)
테스트 2 〉	통과 (0.19ms, 77.3MB)
테스트 3 〉	통과 (0.16ms, 72.3MB)
테스트 4 〉	통과 (0.16ms, 73.2MB)
테스트 5 〉	통과 (0.25ms, 77.1MB)
테스트 6 〉	통과 (0.15ms, 76.9MB)
테스트 7 〉	통과 (0.17ms, 72.3MB)
테스트 8 〉	통과 (0.11ms, 77.7MB)
테스트 9 〉	통과 (0.13ms, 81.9MB)
테스트 10 〉	통과 (0.15ms, 74MB)
테스트 11 〉	실패 (런타임 에러)
테스트 12 〉	통과 (0.23ms, 76.5MB)
테스트 13 〉	통과 (0.18ms, 72.6MB)
테스트 14 〉	실패 (0.10ms, 73.8MB)
테스트 15 〉	통과 (0.14ms, 86.4MB)
테스트 16 〉	실패 (0.09ms, 75.8MB)

채점 결과
정확성: 76.2
합계: 76.2 / 100.0

 

📌 오답 이유

  1. 테스트 1, 테스트 11 런타임 에러
    1. isPrime 메소드 내에서, String n이 int로 변환되기에는 int의 범위를 벗어났을 수도 있겠다고 생각함.
    2. 범위가 더 큰 long으로 수정.
  2. 테스트 14, 16 에러
    1. 일단 이건 런타임 에러 해결하고나서...

 


오답 풀이 2

📌 코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // n진법으로 바꾸기
        String intToString = Integer.toString(n, k);
        char[] intArray = intToString.toCharArray();
        
        StringBuffer sb = new StringBuffer();
        
        for(char a : intArray) {
            
            if(a == '0') {
                if(sb.length()!= 0 && isPrime(sb.toString()))
                    answer++;
                sb.setLength(0);
            } else {
                sb.append(a);
            }
        }
        
        if(sb.length() != 0 && isPrime(sb.toString()))
            answer++;
        
        return answer;
    }
    
    // 해당 숫자가 소수인지, 아닌지 판별하는 메소드
    private boolean isPrime(String n) {
        
        long number = Long.parseLong(n);
        // 런타임 오류 해결을 위해 int -> long으로
        
        if(number < 2) return false;
        if(number == 2) return true;
        
        long sqrt = (long)Math.sqrt(number);
        
        for(int i=2; i<sqrt; i++) {
            if(number % i == 0) return false;
        }
        
        return true;
    }
    
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (12.67ms, 74.1MB)
테스트 2 〉	통과 (0.16ms, 81.5MB)
테스트 3 〉	통과 (0.18ms, 79.6MB)
테스트 4 〉	통과 (0.21ms, 74MB)
테스트 5 〉	통과 (0.22ms, 86.9MB)
테스트 6 〉	통과 (0.16ms, 85MB)
테스트 7 〉	통과 (0.22ms, 77.4MB)
테스트 8 〉	통과 (0.14ms, 70.9MB)
테스트 9 〉	통과 (0.17ms, 74.8MB)
테스트 10 〉	통과 (0.19ms, 80.6MB)
테스트 11 〉	통과 (0.16ms, 73.3MB)
테스트 12 〉	통과 (0.12ms, 73.2MB)
테스트 13 〉	통과 (0.22ms, 80MB)
테스트 14 〉	실패 (0.17ms, 72.2MB)
테스트 15 〉	통과 (0.16ms, 85.2MB)
테스트 16 〉	실패 (0.17ms, 73.5MB)

채점 결과
정확성: 89.3
합계: 89.3 / 100.0

 

📌 오답 이유

  1. 테스트 14, 테스트 16 런타임 에러
    1. isPrime 내 for문의 조건식을 보니, 제곱근을 포함하지 않고 있었다.
    2. number가 제곱근으로 나누어지면 소수로 판별되어야 하는데, 그러지 못하고 있음. 

 


[ 좋은 풀이 ]

 

풀이자 이름

📌 코드

class Solution {
    public int solution(int n, int k) {

        int ans = 0;
        String temp[] = Integer.toString(n, k).split("0");

        Loop : for(String t : temp) {
            if(t.length() == 0) continue;
            long a = Long.parseLong(t);
            if(a == 1) continue;
            for(int i=2; i<=Math.sqrt(a); i++)
                if(a%i == 0) continue Loop;

            ans++;
        }
        return ans;
    }
}

[배운 점]

 

📌 배운 것

  1. 반복문에 이름(?) 을 달아줄 수 있음! - 이름 붙은 반복문
    • 이를 통해 여러 개의 반복문이 중첩되어 있을 경우, continue와 break를 사용할 때 어떤 반복문을 벗어나는 지 등을 지정해줄 수 있음.
    • https://eunzzzzz1.tistory.com/42
  2. 해당 수가 소수인지 판별하는 방법