프로그래머스 : k진수에서 소수 개수 구하기 풀이 (Java, Python)

 

목차

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

프로그래머스

서론

오늘 알아 볼 것은 자바와 파이썬에서 각각에서의 진수 변환을 어떻게 하는지, 그리고 그 내용을 토대로 이 문제를 풀어볼 것이다

 

자바에서의 진수 변환

먼저 자바에서는 10진수에서 다른 진수로의 변환을 기본 Integer 클래스에서 toString() 메소드를 통해서 스트링 형태의 진수로 반환한다. 다음과 같이 10진수의 숫자 883438을 3진수로 변환시킨다면 아래와 같다.

class Main {
    private static int example = 883438;
    public static void main(String[] args) {
        System.out.println(Integer.toString(example, 3));
    }
}

//출력 : 1122212211221

이 문제에서는 필요 없지만 다시 3진수에서 10진수로 변환하고자 한다면 Integer 클래스의 parseInt()를 통해 바꿀 수 있다.

class Main {
    private static int example = 883438;
    public static void main(String[] args) {
        String numberOfBase3 = Integer.toString(example, 3);

        System.out.println(numberOfBase3);
        System.out.println(Integer.parseInt(numberOfBase3, 3));
    }
}

/* 
출력 :	
1122212211221
883438
*/

파이썬에서의 진수 변환

파이썬에서는 10진수에서 다른 진수로의 변환을 기본 라이브러리에서 지원하지는 않지만 다른진수에서 10진수로의 변환은 지원한다. 먼저 10진수에서 다른 진수로 변환하려면 아래와 같다.

def numberToBase(n, b):
    if n == 0:
        return 0
    digits = []
    while n:
        digits.append(str(n % b))
        n //= b
    return "".join(digits[::-1])

num = 883438
base = 3

print(numberToBase(num, base))

# 출력 : 1122212211221

반대로 다른 진수에서 10진수로 변환은 간단하다. 다음과 같이 int 클래스를 통해서 바로 변환할 수 있다.

def numberToBase(n, b):
    if n == 0:
        return 0
    digits = []
    while n:
        digits.append(str(n % b))
        n //= b
    return "".join(digits[::-1])

num = 883438
base = 3

print(numberToBase(num, base))
print(int(numberToBase(num, base), 3))

'''
출력:
1122212211221
883438
'''

 

 

 

풀이

위와 같이 진수 변환을 알고 있다면 기본적인 로직은 어려울 것이 없다. 주어진 양의 정수 n을 k진수로 바꾸고 변환된 k진수를 0을 기준으로 나누어서 배열을 만든다. 이때 0을 기준으로 배열을 생성하게 되면 빈 문자열이 배열에 추가되므로 빈 문자열을 걸러주고, 나머지 숫자들을 문자열 그대로 10진수라고 생각하고 소수 판별을 해주면 된다.

 

하지만 이 문제 테스트케이스에서 조심해야할 것이 두 가지 있는데 하나는 변환된 진수가 너무 크면 기본적인 소수 판별법으로는 시간초과를 받는다. 따라서 소수의 판별법 중 2부터 자기 자신의 제곱근까지 세는 방법을 택해서 사용하면 O(변수의 제곱근) 시간 안에 통과할 수 있게 된다. 또한 변환된 진수가 너무 크면 기본적으로 Integer가 long type으로 선언되는 파이썬에서는 상관이 없지만, 자바에서는 오버플로우에러가 일어나 특정 테스트케이스를 통과하지 못하게된다. 따라서 다른 진수에서 10진수로 변환시 Integer.parseInt()  대신 Long.parseLong()을 사용하자.

 

자바 풀이

import java.util.*;

class Solution {
    public boolean check(String s) {
        long tmp = Long.parseLong(s);
        boolean flag = true;
        for (int i = 2; i <(int) Math.sqrt(tmp) + 1; i++) {
            if (tmp % i == 0) {
                flag = false;
                break;
            }
        }
        if (tmp == 1) {
            flag = false;
        }
        return flag;
    } 
    
    public int solution(int n, int k) {
        String nStr = Integer.toString(n, k);
        String[] strArr = nStr.split("0");
        int answer = 0;
        for (String s : strArr) {
            if (!s.equals("") && check(s)) {
                answer += 1;
            }
        }

        return answer;
    }
}

 

파이썬 풀이

import math

def check(s):
    a = int(math.sqrt(s)) + 1
    flag = True
    for i in range(2, a):
        if s % i == 0:
            flag = False
            break
    if s == 1:
        flag = False
    return flag

def numberToBase(n, b):
    if n == 0:
        return 0
    digits = []
    while n:
        digits.append(str(n % b))
        n //= b
    return "".join(digits[::-1])

def solution(n, k):
    new = numberToBase(n, k)
    answer = 0
    tmp = new.split("0")
    for i in tmp:
        if i != "":
            if check(int(i)):
                answer += 1
                

    return answer

 

결론

자바로 문제를 풀다보면 생각보다 숫자 타입에서 오버플로우를 자주 만나게 되는데 문제를 잘 읽고 제한사항에서 숫자의 크기를 잘 확인하여야 한다. 위와 같은 경우에서 처럼 int 타입의 제한 범위를 훨씬 넘는 경우가 있기 때문에 타입 지정을 잘해주어야 한다.