[카카오 코딩 테스트 2022 신입 공채] k 진수에서 소수의 개수 구하기

 

링크

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

문제

 

 

풀이

 

-양의 정수 n이 주어집니다.
-이 숫자를 k진수로 바꿉니다.
-변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 봅니다.

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

 

1. 양의 정수 n이 주어집니다.

첫 번째 n: 437674
두 번째 n: 110011

 

2. 이 숫자를 k진수로 바꿉니다.

첫 번째 k: 3
첫 번째 n을 첫 번째 k진수로 바꿉니다.
-> 437674를 3진수로 바꿉니다.

두 번째 k: 10
두 번째 n을 두 번째 k진수로 바꿉니다.
-> 110011를 10진수로 바꿉니다.

 

3. 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 봅니다.

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

0을 기준으로 숫자를 나눠서 해당 숫자가 소수인지 판별하는 방법입니다.

 

첫 번째 n인 437674를 3진수로 변환하면 211020101011입니다.
211020101011의 경우는 211020101011 0을 기준으로 211, 2, 1, 1, 11 총 5개의 수가 나옵니다.

첫 번째 211은 소수입니다.
두 번째 2는 소수입니다.
세 번째 1은 소수가 아닙니다.
네 번째 1은 소수가 아닙니다.
다섯 번째 11은 소수입니다.​
그러므로 211020101011의 5개 의 숫자 중 3개의 소수가 있습니다.

위의 입출력 예와 같이 437674를 3진수로 변환 후 소수를 구했을 때 답은 3이 나옵니다.

두 번째 n인 110011를 10진수로 변환하면 110011입니다.
110011의 경우는 110011 양 쪽 11과 11이 조건에 맞는 수 입니다
첫 번째 11은 소수입니다.
두 번째 11은 소수입니다.
그러므로 110011의 양 쪽에 소수가 하나씩 있으므로 총 2개의 소수가 있습니다.

위의 입출력 예와 같이 110011를 10진수로 변환 후 소수를 구했을 때 답은 2가 나옵니다.

 

---

 

문제 풀이 방법은 위와 같은 순서로 진행될 것입니다.

1. 소수 합계를 반환해줄 answer가 있습니다.
2. 양의 정수 n을 k진수로 변환합니다.
3.k진수로 변환된 n의 소수 합계를 구합니다.
4. 소수 합계를 반환합니다.

import java.util.StringTokenizer;
class Solution {
    
    // 정수 n이 소수인지 판별하는 함수
    public boolean isPrime(Long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        for (int i = 2; i <= Math.sqrt(n); i++) if(n % i == 0) return false;
        return true;
    }

    // 정수 n을 k진수로 변환하는 함수
    public Long toEverynary (int n, int k) {
        return Long.parseLong(Integer.toString(n,k));
    }
    
    public int solution(int n, int k) {
        int answer = 0;// 소수 합계
        
        // toEverynary 함수는 의 정수 n을 k진수로 변환합니다. 
        // StringTokenizer를 "0"으로 구분하여 생성하면 0 을 제외한 값으로만 값이 생성됩니다.
        // 만약 split("0")으로 처리한다면 0이 연속으로 나오는 0000 의 경우 빈 공백의 배열이 생성될 것입니다.
        StringTokenizer token = new StringTokenizer(Long.toString(toEverynary(n, k)), "0");
        
        // token안에 담긴 수 만큼 반복문을 실행하여 해당 수가 소수인지 판별 후 소수인 경우만 소수 합계에 더해줍니다.
        while (token.countTokens() > 0) {
            if (isPrime(Long.parseLong(token.nextToken()))) answer++;
        }
        return answer;// 소수 합계를 반환합니다.
    }
}

 

주석 없는 버전

import java.util.StringTokenizer;
class Solution {
    public boolean isPrime(Long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        for (int i = 2; i <= Math.sqrt(n); i++) if (n % i == 0) return false;
        return true;
    }

    public Long toEverynary (int n, int k) {
        return Long.parseLong(Integer.toString(n,k));
    }
    
    public int solution(int n, int k) {
        int answer = 0;
        StringTokenizer token = new StringTokenizer(Long.toString(toEverynary(n, k)), "0");
        while (token.countTokens() > 0) {
            if (isPrime(Long.parseLong(token.nextToken()))) answer++;
        }
        return answer;
    }
}

 

---

 

후기

* 난이도 (5점 만점)

5 : 풀 줄 알면 기업 코딩 테스트는 문제없음.

4 : 평균적인 기업 코딩 테스트의 중간 이상.

3 : 평균적인 기업 코딩테스트의 쉬운 문제.

2 : 알고리즘 문제를 연습하고 있다면 풀 수 있는 문제.

1 : 시간이 오래 걸리지 않고, 누구나 풀 수 있는 문제.

 

이 문제는 "k진수"라는 단어와 "소수 판별"이라는 단어에 겁먹지 않는다면 충분히 풀 수 있는 문제입니다.
문제를 풀 때 한 번에 모든 것을 해결하려 하지 말고 단계 별로 풀이를 정해서 차근차근 풀어나간다면 어렵지 않은 문제입니다.