[2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기

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

프로그래머스

 

풀이

진법변환, 소수판별은 자주 등장하는 부분이라 비교적 쉽게 구현했다. 소수의 판별 조건이 약간 까다로웠는데 가능한 시나리오들을 차근차근 생각해봤다.

 

1. 진법변환

2. 앞에서부터 살펴보는데

 1) 맨 앞인 경우 -> P0, P 케이스가 등장할 수 있다.

    - P0 : 뒷 숫자에서 0이 등장하는 경우, 그 앞까지의 숫자가 소수인지 체크

    - P : 숫자 끝까지 0이 등장하지 않는 경우, 해당 숫자 자체가 소수인지 체크

 2) 0이 한번이라도 등장한 경우 -> 0P0, 0P 케이스가 등장할 수 있다.

   - 0P0 : 0이 한번 더 등장한 경우, 0과 0 사이의 숫자가 소수인지 체크

   - 0P : 숫자 끝까지 0이 한번 더 등장하지 않은 경우, 0 뒤의 숫자가 소수인지 체크

 

따라서 가능한 경우를 flag로 만들어서 체크해줘야 할 때마다 체크해줬다. 요즘 디버깅 안하고 프로그래머스 내에서 최대한 풀어보려고 하다 보니 print 문을 섞어서 실행했다. 두가지 버전 모두 기록해두려고 한다!

 

주의할 점은 소수인지 체크할 숫자를 담는 문자열이 빈 문자열인 경우 소수 체크를 하지 않고 넘어가줘야 한다. (코드 내 check_num != '' 조건)

ex. P0 경우가 등장하여 check_num이 빈 문자열로 초기화되었는데 그 뒤에 다시 0이 등장하면 빈 문자열이 isPrime 함수로 넘어가 형변환 에러가 발생한다. 

 

중간에 10분정도 쉬다가 다시 풀었는데 한 1시간정도 걸렸다.

 

python 코드 (print 출력문 O)

# 진법 변환
def convert(n, k):
    result = ''
    q, r = divmod(n, k)
    result += str(r)
    
    while q != 0:
        q, r = divmod(q, k)
        result += str(r)
    
    return result[::-1]

# 소수 판별 (제곱근까지만 판단)
def isPrime(num):
    if num == 0 or num == 1:
        return False
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            # 소수 아님
            return False    
    return True

def solution(n, k):
    answer = 0
    
    converted_n = convert(n, k)
    
    check_num = ''
    
    flag_0P0 = False
    flag_P0 = False
    flag_0P = False
    flag_P = False
    
    for i in range(len(converted_n)):
        print("------")
        print(flag_0P0,flag_P0,flag_0P,flag_P)
        print(check_num)
        print("------")
        
        # 맨 앞인 경우
        if i == 0:
            # P0, P 가능
            check_num += converted_n[i]
            flag_P, flag_P0 = True, True
            continue
        
        if converted_n[i] == '0':
            flag_P = False
            flag_0P = True
            # 만약 맨앞에서부터 보던 중이었다면
            if flag_P0:
                print("PO case", check_num)
                if isPrime(int(check_num)):
                    print("PO Hit", check_num)
                    answer += 1
                check_num = ''
                flag_0P0, flag_P0 = True, False
                continue
            
            # 한번이라도 0이 등장한 적이 있다면
            elif flag_0P0 and check_num != '':
                print("0PO case", check_num)
                if isPrime(int(check_num)):
                    print("0PO Hit", check_num)
                    answer += 1
                check_num = ''
        else:
            check_num += converted_n[i]
        
    
    # 맨 뒤까지 다 봤는데 0이 안나온 경우였다면, P 경우 체크
    if flag_P and check_num != '' and isPrime(int(check_num)) :
        answer += 1
        print("P Hit", check_num)
    # 맨 뒤까지 다 봤고 0P가 가능한 경우
    if flag_0P and check_num != '' and isPrime(int(check_num)) :
        answer += 1
        print("0P Hit", check_num)
        
    return answer

 

python 코드 (깔끔 ver)

# 2022-09-20
# 2022 카카오 테크 인턴십 기출 - k진수에서 소수 개수 구하기 (프로그래머스 lv2)
# https://school.programmers.co.kr/learn/courses/30/lessons/92335
# 소요 시간 : 15:17 ~ 16:06, 16:21~16:31 (60m)

# 진법 변환
def convert(n, k):
    result = ""
    q, r = divmod(n, k)
    result += str(r)

    while q != 0:
        q, r = divmod(q, k)
        result += str(r)

    return result[::-1]


# 소수 판별 (제곱근까지만 판단)
def isPrime(num):
    if num == 0 or num == 1:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            # 소수 아님
            return False
    return True


def solution(n, k):
    answer = 0

    converted_n = convert(n, k)

    check_num = ""

    flag_0P0 = False
    flag_P0 = False
    flag_0P = False
    flag_P = False

    for i in range(len(converted_n)):
        # 맨 앞인 경우
        if i == 0:
            # P0, P 가능
            check_num += converted_n[i]
            flag_P, flag_P0 = True, True
            continue

        if converted_n[i] == "0":
            flag_P = False
            flag_0P = True
            # 만약 맨앞에서부터 보던 중이었다면
            if flag_P0:
                if isPrime(int(check_num)):
                    answer += 1
                check_num = ""
                flag_0P0, flag_P0 = True, False
                continue

            # 한번이라도 0이 등장한 적이 있다면
            elif flag_0P0 and check_num != "":
                if isPrime(int(check_num)):
                    answer += 1
                check_num = ""
        else:
            check_num += converted_n[i]

    # 맨 뒤까지 다 봤는데 0이 안나온 경우였다면, P 경우 체크
    if flag_P and check_num != "" and isPrime(int(check_num)):
        answer += 1
    # 맨 뒤까지 다 봤고 0P가 가능한 경우
    if flag_0P and check_num != "" and isPrime(int(check_num)):
        answer += 1

    return answer