프로그래머스 > 코딩테스트 연습 (23.04.08) > 2022 Kakao Blind Recruitment > k진수에서 소수 개수 구하기 (Lv.2)

프로그래머스

---

첫번째 시도

# 소수이면 True, 소수가 아니면 False 반환 함수

def checkPrime(num):
    if num == 1 or num == 0:
        return False
    # elif num == 2:
    #     return True
    for i in range(2, int(num):
        if num%i == 0:
            return False
    return True

함수를 만드는 건 뚝딱 만들었지만, 이 함수로 인해 시간을 엄청 잡아먹었다. 자세한 건 세번째 시도를 참고하면 된다.

# 함수 changeNumSys
# input : n, k = 437664, 3
# return : kSys =[2, 1, 1, 0, 2, 0, 1, 0, 0, 2, 1, 0]

# 함수 splitNum
# input : kSys = [2, 1, 1, 0, 2, 0, 1, 0, 0, 2, 1, 0]
# output : primeNum = [211, 2]

# 함수 changeNumSys

while True:
    quotient = n//k
    remainder = int(n%k)

    if quotient < k:
        kSys.insert(0, remainder)
        kSys.insert(0, quotient)
        break
    kSys.insert(0, remainder)
    n = quotient

# 함수 splitNum

tempNum = 0
for num in arr:
    if num == 0:
        if checkPrime(tempNum) :
            primeNum.append(tempNum)
        tempNum = 0
    else:
        tempNum *= 10 
        tempNum += num 
if checkPrime(tempNum):
    primeNum.append(tempNum)

두 함수 사용하여 나온 primeNum = [211, 2]의 길이를 반환하면 소수의 개수를 정답으로 제출할 수 있다.

>> 시간 초과 에러 발생

>> '현재 숫자 + 이전 숫자'처럼 숫자를 문자 타입으로 더했더니 int(문자 타입 숫자)로 형변환을 시도했을 때,   "ValueError: invalid literal for int() with base 10:"  가 발생했다.  int("문자") 로 했을 때와 똑같은 에러다. 숫자여도 문자열로 더해진 숫자는 문자로 인식하는 듯 하다. 그래서 '10 * 현재 숫자 + 이전 숫자'로 바꾸어 처음부터 끝까지 숫자처럼 사용했다.

두번째 시도

함수를 하나로 합치면 반복문 실행 수도 줄일 수 있을거라 생각했다. changeNumSys 함수와 splitNum 함수, 그리고 solution 함수까지 모두 합쳤다.

def solution(n, k):
    temp, i = 0, 1
    primes = []

    while True:
        quotient = n//k
        remainder = int(n%k)

        if remainder == 0 :
            if checkPrime(temp):
                primes.append(temp)
            temp, i = 0, 1
        else:     
            temp += remainder * i
            i *= 10
        
        n = quotient
        
        if quotient < k:
            temp += quotient * i
            if checkPrime(temp):
                primes.append(temp)
            break

    return len(primes)

>> 그래도 시간이 초과되었다!

 

세번째 시도

소수인지 아닌지 확인하는 함수의 기존 로직은 2부터 num-1까지 나누어서 나머지가 0이 되는, 즉 나누어떨어지는 숫자가 나오면 반복문이 멈추고 False를 반환하고 나누어떨어지는 숫자가 없으면 True를 반환하는 방식이었다. 

입력 숫자(num)에서 2부터 num-1 까지
나누어떨어지는 숫자 존재 >> False
나누어떨어지는 숫자 없음 >> True (소수)

여기서 시간이 오래 걸리는 이유는 아주아주아주 큰 소수일 경우, 2부터 해당 숫자까지 반복을 하면서 시간이 많이 소요되었기 때문이었다. 나누는 수를 줄일 수 있는 방법을 찾았다. 

24의 약수를 찾을 때
1 24
2 12
3 8
4 6
6 4
8 3
12 2
24 1
이렇게 짝을 찾아간다.

만약 64처럼 제곱 수일 경우
1 64
2 32
4 16
8 8
까지 확인하면 이후부터는 순서만 바뀔 뿐이다.

>> 2부터 4까지 나누어 떨어지는지 확인을 하면, 6부터 24까지는 확인을 하지 않아도 나누어 떨어지는 숫자가 있는지 없는지를 알 수 있다. 즉, 2부터 입력 숫자의 제곱근까지만 확인을 하면 된다!

# checkPrime 함수

for i in range(2, int(math.sqrt(num))+1):
    if num%i == 0:
        return False

 

---

GitHub - buji-learn/1percentmore38timesbetter