[프로그래머스] LV2 > 완전탐색 > 소수 찾기

프로그래머스 > 완전탐색 > 소수찾기

프로그래머스

 

소수를 만들기 위한 조합을 만들고 소수의 수를 count해 출력하는 문제이다.

 

초기에 코드를 짜다 자체적으로 7자리의 수의 모든 조합을 만드는 것은 힘들다 생각해 itertools의 permutauions를 사용하였다.

from itertools import permutations

def solution(numbers):
    L = list(numbers)
    per = []
    answer=0
    for i in range(1,len(L)+1):
        per += list(map(''.join,permutations(L,i))) 
        
    per = list(map(int, per))
    per = list(set(per))
    per.sort()
    #print(per)
    
    for i in per:
        check = True
        if (i == 1) or (i == 0):
            continue 
        elif i == 2:
            answer += 1
        else:
            for j in range(2, i):
                if ((i / j) == (i//j)):
                    print(i, j, i/j, i//j)
                    check = False
                    break
                else:
                    check = True
        
        if check == True:
            answer+=1
    return answer

print(solution('130'))

 

if ((i / j) == (i//j)):의 경우 비효율적이라 생각이되어 if i%j ==0: 으로 수정하였다.

테스트케이스는 성공했지만 정답제출시 통과하지 못해 다시 오류가 나는 부분을 찾아다녔다.

오류가 난 부분은 2를 예외처리할 때 answer += 1이라 해주었는데 check값은 True기 때문에 마지막 if 문에서 결국 +1이 더 되었다.

이를 해결하기 위해 다음과 같이 수정하였다.

 

from itertools import permutations

def solution(numbers):
    L = list(numbers)
    per = []
    answer=0
    for i in range(1,len(L)+1):
        per += list(map(''.join,permutations(L,i))) #(모든 경우의 조합찾기)
        
    per = list(map(int, per)) # int형 자료로 변환
    per = list(set(per)) # 중복제거
    per.sort() #정렬
    print(per)
    
    for i in per:
        check = True
        if (i == 1) or (i == 0):
            continue 
        elif i == 2:
            # answer += 1 #문제가 된 부분
            check = True
        else:
            for j in range(2, i):
                if (i % j == 0): #소수인지 아닌지 확인
                    check = False
                    break #소수라면 멈추고 다음 for문 진행
                else:
                    check = True
        
        if check == True: #소수라면 answer에 +1
            answer+=1
    return answer

 

이제 불 필요한 부분을 없애고 최적화를 해보겠다.

from itertools import permutations
def prime_check(i): #소수 판별을 함수화 / return하여 bool 값을 저장
    if (i == 1) or (i == 0):
        return False
    elif i == 2:
        return True
    else:
        for j in range(2, i):
            if (i % j == 0):
                return False
    return True

def solution(numbers):
    L = list(numbers)
    per = []
    answer=0
    for i in range(1,len(L)+1):
        per += list(map(''.join,permutations(L,i))) 
        
    per = sorted(set(map(int, per))) # int형 변형, 중복제거, 정렬을 한줄로 처리(계산 시간이 소폭 줄어듬)
    
    for i in per:
        if prime_check(i) == True:
            answer+=1
    return answer

 

다음과 같이 마무리하였다.