[프로그래머스] k진수에서 소수 개수 구하기

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

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

 

 

<문제 설명>

주어진 n을 k진수로 바꾼 뒤 바꾸어진 수에서 각 자리수에 0을 포함하지 않는 소수의 개수를 찾는 것이다.

 

 

<문제 이해>

먼저 n을 k진수로 변환한 수를 문자열로 얻어, 0을 기준으로 나누어

나누어진 수가 소수인지 아닌지 판별하면 된다고 생각했다.

 

 

 

<문제 풀이1>

def solution(n, k):
    tn = ''
    
    while n > 0:
        tn = str(n%k) + tn
        n = n // k
        
    cnt = 0
    for pn in tn.split('0'):
        temp = 1
        if pn in ['','1']: continue;
        
        num = int(pn)
        for i in range(2,num):
            if num % i == 0: temp = 0; break;
        
        cnt += temp
        
    return cnt

 

<문제 풀이2>

def solution(n, k):
    temp = ''
    cnt = 0    

    while n > 0:
        x = str(n%k)
        n = n // k
        
        if x != '0': 
            temp = x + temp
            if n != 0: continue
        
        if temp not in ['','1'] :
            isPn = 1
            for i in range(2, int(temp)):
                if int(temp) % i == 0 :
                    isPn = 0; break;
            cnt += isPn
        
        temp = ''
                
    return cnt

여러 가지 방법으로 풀어봤지만 둘 다 실패했다. 

그래서 결국 다른 사람들의 풀이를 봤고 코드를 고쳤더니 문제를 완벽히 풀 수 있었다.

 

 

 

<풀이 개선>

문제는 소수를 판별해 내는 코드였다.

원래 하던대로 판별해내려는 수를 2에서 그 수까지 for문을 돌렸으나, 이것이 문제였다.

다른 사람 풀이를 보기 전에 문제 해설을 보았는데, 키포인트가 자료형과 소수를 판별해내는 것이였다.

파이썬이기 때문에 자료형은 전혀 문제되지 않을 것이라고 생각했고,

소수를 구하는 방법을 설명해주는 문구를 보고 어디가 잘못된 것인지 짐작은 했으나, 끝까지 해결은 못했다.

그것을 다른 사람들의 풀이를 보고 깨달았다.

 

def solution(n, k):
    tn = ''				# k진수 변환할 문자 들어갈 빈 문자열 
    
    while n > 0:			# k진수로 변환하기
        tn = str(n%k) + tn
        n = n // k
        
    cnt = 0
    for pn in tn.split('0'):			# 0을 기준으로 문자열 분리
        temp = 1				# 소수 여부 판단 변수. 소수면 1 아니면 0
        if pn in ['','1']: continue;		# ''거나 '1'이면 다음으로 넘어감
        
        num = int(pn)				# ''거나 '1'이 아닐 경우, 숫자로 변환
        for i in range(2,int(num**(1/2))+1):	# 소수인지 판별
            if num % i == 0: temp = 0; break;	# 소수가 아니면 temp = 0
        
        cnt += temp				# 값을 더해줌
        
    return cnt

 

해설에 2부터 루트를 씌운 값까지 for문을 돌리면 된다고 써있어서 math.sqrt를 사용했으나 

틀려서 그냥 다른사람의 풀이를 보았다*^^*

sqrt대신에 **를 이용해 값을 똑같이 만들어줄 수 있는 것을 발견해 이것을 적용했다.

그리고 1을 꼭 더해주어야 한다. 이거 안해주면 틀린다.

암튼 많은 것을 배웠다^^