진수 변환 알고리즘 활용하기

1. 문제

 

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

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

 

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수가 몇개 인지 알아보려 합니다.

 

0P0 처럼 소수 양쪽에 0이 있는 경우

 

P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우

 

0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우

 

P처럼 소수 양쪽에 아무것도 없는 경우

 

단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.

 

예를 들어 101은 P가 될 수 없습니다

 

예를 들어 437674를 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211,2,11이 있으며 총 3개입니다.

 

211,2,11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.

 

211은 P0형태에서 찾을 수 있고 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

 

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return하도록 solution 함수를 완성하세요.

 

 

2. 제한사항

 

n은 1이상 1000000이하

 

k는 3이상 10이하

 

 

3. 예시

 

 

4. 나의 풀이

 

주어진 수를 k진법으로 바꾸는 알고리즘을 생각해야한다

 

주어진 수 n을 k로 나눈 몫과 나머지가 d1와 r1이면 r1을 옆에 두고 d1를 다시 k로 나눈다

 

d1를 k로 나눈 몫과 나머지가 d2, r2이면 r2를 옆에 두고 d2를 다시 k로 나눈다

 

이 과정에서 몫이 0이 될때까지 반복한다

 

그럴때 나오는 나머지가 rn, rn-1, rn-2, ..., r1이고 그러면 n을 k진법으로 바꾼 수는...

 

$r_{n}r_{n-1}r_{n-2}....r_{1}$

 

 

n을 k진법으로 바꾼 수가 change_n이라고 한다면 숫자를 붙이기에는 문자열이 좋으니까 문자열로 초기화

 

def solution(n,k):
    
    answer = 0
    
    change_n = ''
    
    while 1:
        
        n,r = divmod(n,k)
        
        change_n += str(r)
        
        if n < k:
            
            change_n += str(n)
            
            break
            
    change_n = change_n[::-1]

 

위에서 설명한 알고리즘대로 n을 k로 나눈 몫과 나머지를 d와 r이라고 하면

 

r은 문자열로 바꾸고 change_n에 더해주고

 

몫 d는 다시 정수 n으로 저장한다

 

위 과정을 계속 반복하여 만약 나눗셈을 실행한 뒤에...

 

n < k라면 또 나눗셈을 수행하면 몫이 0이 될 것이므로 더 이상 나눗셈을 수행하지말고

 

n을 바로 change_n에 더해준다

 

만약 나눗셈을 수행해버리면 change_n에 '0'이 더해져서 k진법 수 앞자리가 0으로 시작하니 골치아파진다

 

아무튼 change_n은 현재 거꾸로 붙여져있으므로 이걸 다시 역순으로 배열시켜야한다

 

그것은 change_n = change_n[::-1]로 가능

 

근데 여기서 k=10일 수 있다는 점이다. 그러면 굳이 알고리즘을 수행할 필요가 없이 바로 str(n)으로 변환하면 된다

 

def solution(n,k):
    
    answer = 0
    
    change_n = ''
    
    if k != 10:
    
        while 1:

            n,r = divmod(n,k)

            change_n += str(r)

            if n < k:

                change_n += str(n)

                break

        change_n = change_n[::-1]
    
    else:
        
        change_n = str(n)

 

그러면 이제 소수를 찾아야할텐데 매번 소수를 판별하는 코드를 작성해야하므로 그냥 하나의 함수를 만든다

 

소수 판별 알고리즘은 n을 2부터 n-1까지로 하나씩 나눠보면서 나누어떨어지는 수가 발견되면 소수가 아니고 발견되지 않으면 소수이다.

 

그런데 이미 sqrt(n)까지만 나눠봐도 된다는 점을 배웠다

 

def solution(n,k):
    
    answer = 0
    
    def prime(n):
        
        if n == '1':
            
            return False
        
        else:
            
            n = int(n)
            
            for i in range(2,int(n**(1/2))+1):
                
                if n % i == 0:
                    
                    return False
            
            return True
    
    change_n = ''
    
    if k != 10:
    
        while 1:

            n,r = divmod(n,k)

            change_n += str(r)

            if n < k:

                change_n += str(n)

                break

        change_n = change_n[::-1]
    
    else:
        
        change_n = str(n)

 

prime(n)이라는 함수를 만든다

 

n은 문자열로 들어올 것이라고 생각한다

 

n이 '1'이면 소수가 아니니까 False를 return하고 '1'이 아니면 소수인지 검사를 한다

 

먼저 문자열로 들어온다고 생각하므로 n= int(n)으로 정수형 변환한다

 

2부터 sqrt(n)까지 for문을 순회하여 i라고 한다

 

n을 i로 나눠봐서 나머지가 0이면 소수가 아니므로 바로 False를 return하고

 

for문을 무사히 돌았다면 나누어 떨어지는 수가 존재하지 않으므로 소수라는 뜻이고 True를 return한다

 

---------------------------------------------------------------------------------------------------------

 

이제 소수를 찾아야하는데...

 

큐/스택 기술을 이용하자

 

진법변환한 n을 하나씩 for문으로 순회해서 i라고 하면 만약 i가 '0'이 아니면 stack에 그대로 쌓고

 

만약 i가 '0'이라면 stack에 쌓여있는 수를 하나로 합쳐서 소수인지 검사하면 된다

 

이러면 모든 조건을 만족시킬 수 있다

 

일단 어차피 내가 만든 진법변환 수는 0으로 시작하지 않는다

 

21102010201302...라고 한다면

 

처음에는 2,1,1이 들어가다가 이제 0차례인데

 

그러면 이미 들어간 211은 P0의 형태

 

다음에 들어갈 수는 무조건 0P의 형태이거나 0P0의 형태가 된다

 

실제로 다음에 들어갈 2는 0P0의 형태가 된다

 

여기서 중요한점은 0으로 끊기때문에 P에 0이 들어갈 수가 없다

 

P에 0이 들어가더라고 그걸 0을 기준으로 0P'0이나 0P'나 P'0으로 나뉜다

 

--------------------------------------------------------------------------------------

 

def solution(n,k):
    
    answer = 0
    
    def prime(n):
        
        if n == '1':
            
            return False
        
        else:
            
            n = int(n)
            
            for i in range(2,int(n**(1/2))+1):
                
                if n % i == 0:
                    
                    return False
            
            return True
    
    change_n = ''
    
    if k != 10:
    
        while 1:

            n,r = divmod(n,k)

            change_n += str(r)

            if n < k:

                change_n += str(n)

                break

        change_n = change_n[::-1]
    
    else:
        
        change_n = str(n)
        
    n_list = []
    
    for num in change_n:
    
        if n_list == []:
            
            if num != 0:
                
                n_list.append(num)
        
        else:
            
            if num != 0:
                
                n_list.append(num)
            
            else:
                
                prime_n = ''.join(n_list)
                
                if prime(prime_n):
                    
                    answer += 1
                
                n_list = []

 

stack을 n_list라고 하고 change_n을 for문으로 하나씩 순회하여 num이라고 하자

 

n_list가 비어있냐 비어있지않냐로 나뉜다

 

비어있다면 일단 num을 넣는것만 생각해야하는데 물론 '0'이면 넣지않는다

 

n_list가 비어있지 않다면.. num이 '0'이 아니면 집어넣고

 

'0'인 순간 이제 n_list를 ''.join(n_list)로 합쳐서 prime함수에 집어넣는다

 

만약 함숫값이 True이면 합친 수는 소수이므로 answer에 1을 더해준다

 

그렇지 않으면 answer에는 더하지 않는다

 

검사가 끝났으므로 n_list=[]으로 다시 초기화한다

 

-------------------------------------------------------------------------------------

 

근데 이제 for문을 다 돌고나서 n_list가 비어있을수도 있고 비어있지 않을수도 있다

 

마지막이 0으로 끝나면 n_list가 비어있을것이고 0으로 끝나지 않으면 n_list가 비어있지 않을 것이다

 

21102010이면 211, 2,1 검사 끝나고 n_list = []인데... 이제 마지막 0차례인데 얘는 들어가지않고 for문 탈출

 

2110201이면 211,2 검사 끝나고 n_list = []인데.. 0과 1이 남아있는데 0은 들어가지 않고

 

여전히 n_list = []인데

 

마지막 1이 들어가고 for문이 끝난다

 

그래서 for문이 끝나고 나서 n_list가 비어있지 않으면 다시한번 합쳐서 prime함수로 소수인지 검사한다

 

def solution(n,k):
    
    answer = 0
    
    def prime(n):
        
        if n == '1':
            
            return False
        
        else:
            
            n = int(n)
            
            for i in range(2,int(n**(1/2))+1):
                
                if n % i == 0:
                    
                    return False
            
            return True
    
    change_n = ''
    
    if k != 10:
    
        while 1:

            n,r = divmod(n,k)

            change_n += str(r)

            if n < k:

                change_n += str(n)

                break

        change_n = change_n[::-1]
    
    else:
        
        change_n = str(n)
        
    n_list = []
    
    for num in change_n:
    
        if n_list == []:
            
            if num != 0:
                
                n_list.append(num)
        
        else:
            
            if num != 0:
                
                n_list.append(num)
            
            else:
                
                prime_n = ''.join(n_list)
                
                if prime(prime_n):
                    
                    answer += 1
                
                n_list = []
                
                
    if n_list != []:
        
        prime_n = ''.join(n_list)
        
        if prime(prime_n):
            
            answer += 1
            
    return answer

 

5. 다른 풀이

 

좋아요를 가장 많이 받은 풀이를 보면 내 알고리즘이랑 동일하지만 코드가 조금 더 간결하다

 

def conv(n, k):
    s = ''
    while n:
        s += str(n%k)
        n //= k
    return s[::-1]

# n이 소수인지 판정
def isprime(n):
    if n <= 1: return False
    i = 2
    while i*i <= n:
        if n%i == 0: return False
        i += 1
    return True

def solution(n, k):
    s = conv(n,k)
    cnt = 0
    for num in s.split('0'):
        if not num: continue # 빈 문자열에 대한 예외처리
        if isprime(int(num)): cnt += 1
    return cnt

 

conv함수는 진법변환함수인데 while n:을 했다는 것은 n이 0이 되면 반복문을 탈출하게 된다

 

n을 k로 나눈 나머지(%)를 문자열로 변환해서 s에 더해주고 n은 k로 나눈 몫(//)을 n으로 만든다

 

그리고 역배열시킨 s[::-1]을 return하면 진법변환

 

isprime은 소수인지 확인하는 함수

 

얘가 조금 특이한데???

 

일단 n이 1이하이면 소수가 아니니까 바로 False를 return하고

 

1보다 크면 이제 i=2라 하고

 

n을 i로 나눈 나머지가 0이면 소수가 아니니까 바로 False를 return하고 그렇지 않으면 i에 1을 더해가서 반복을 해

 

그런데 반복 종료 조건이 i의 제곱이 n보다 크면??

 

$i^{2} > n$은 $i > \sqrt{n}$랑 동치니까 결국 i가 sqrt(n)일때까지 반복한다는 소리

 

결국엔 똑같긴하네?

 

다음 solution함수를 보면

 

n을 k진법으로 변환한 s를 구하고 s.split('0')가 재밌네

 

내가 stack으로 길게 쓴 코드가 결국 s.split('0')랑 똑같잖아??? 허허

 

 

6. 되돌아보기

 

stack기술이 s.split('0') 하나로 끝나버렸다... 하하

 

진법변환 알고리즘

 

n을 k로 나눈 나머지를 이어붙이고 마지막에 s[::-1]로 역순배열!

 

소수 판별 알고리즘

 

sqrt(n)까지만 검사해보면 끝!