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

2
post-thumbnail

안녕하세요. 오늘은 프로그래머스의 k진수에서 소수 개수 구하기
문제를 풀어보겠습니다. 이 문제는 2022년도 KAKAO BLIND RECRUITMENT에서 출제되었습니다.


1) 문제 링크

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

2) 문제 풀이

✔ n을 k진수로 바꾼 후, String으로 return

주어진 n을 k진수로 변환합니다.(변환하는 함수 convertNumber) k진수로 변환한 후, 문제 풀이의 편의성을 위해 해당 숫자를 String으로 치환해서 return합니다.

✔ return결과를 "0"으로 split

n을 k진수로 바꾼 String을 "0"으로 split합니다. String을 일일이 돌면서 "0"을 체크하기보다, 그냥 split하면 시간을 훨씬 많이 단축할 수 있습니다.

✔ split한 String Array를 돌면서 소수 여부 확인

split한 값들은 String 배열에 담깁니다. 해당 배열을 돌면서 배열 속 숫자의 소수 여부를 확인합니다. 이 때, 2부터 소수의 제곱근까지만 확인해보면 소수 여부를 알 수 있습니다.

3) 전체 코드

class Solution {
   public int solution(int n, int k) {
        int answer = 0;
        String convertedNum = convertNumber(n, k);
        String[] splitedNum = convertedNum.split("0");

        for (String str : splitedNum) {
            if ("".equals(str)) {
                continue;
            }
            if(isSosu(Long.parseLong(str))) {
                answer++;
            }
        }

        return answer;
    }

    private boolean isSosu(long num) {
        if(num == 1) return false;

        int limit = 2;

        while (limit <= Math.sqrt(num)) {
            if(num % limit == 0) {
                return false;
            }
            else {
                limit ++;
            }
        }

        return true;
    }

    private String convertNumber(int n, int k) {
        if(k == 10) return Integer.toString(n);

        StringBuilder sb = new StringBuilder();

        while (n > 0) {
            sb.append(n % k);
            n /= k;
        }

        return sb.reverse().toString();
    }
}

4) 느낀점

✔ 틀린 이유

처음에 제출했을 때 1번 테스트 케이스가 시간초과 나고 11번 테스트 케이스가 틀렸습니다. 문제는 두 가지였습니다.

1. 소수 판별 로직 개선 필요

초기에는 소수 판별 로직의 while문 범위를 2부터 n/2까지로 잡았습니다. 그랬더니 1번 테스트케이스에서 시간초과가 났습니다. 답 확인 결과 n의 제곱근까지만 범위를 잡아도 소수를 판별할 수 있었습니다.

2. n을 k진수로 변환한 String을 그냥 탐색하면서 "0"을 찾음

초기에는 n을 k진수로 변환한 결과값의 자릿수를 for문을 돌면서 한 자리씩 탐색했습니다. 답을 확인해보니 매우 비효율적인 풀이였고, 그냥 split을 쓰면 로직이 많이 단축될 수 있는 문제였습니다.


[참고한 곳]
https://velog.io/@ujone/%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-JAVA

0개의 댓글