[알고리즘 풀이] 프로그래머스 : 소수 찾기, Level2(완전탐색)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3

알고리즘 연습 - 소수 찾기 | 프로그래머스

아래 2가지 과정으로 문제를 단순화 해서 풀었음

 

1. 전체 순열리스트 구하기

2. 소수 판별

 

위 2개만 보면 아주 간단해 보이는데, 저 2개 구현하는게 생각보다 간단하지 않아서

문제푸는데 오래걸렸음.

 

 

 - 전체 순열리스트 구하기는 itertools의 permutations를 사용해서 구함

 - 소수판별은 에라토스테네스의 체 방식으로

  * 판별하려는 수(이하 판별수)를 2부터 판별수의 제곱근으로 나누어 나머지가 0인 경우가 나오면 소수가 아님

 

permutations를 사용안하면 문제푸는데 상당히 오래걸릴 듯 싶다.

 

아래는 코드

from itertools import permutations
 
def solution(numbers):
    
    # 소수 판별할 리스트 만들기
    num_list = [] # 전체 순열 넣어줄 리스트
    for i in range(1,len(numbers)+1) :
        test_list = permutations(numbers,i)       
        for j in test_list :
            num_list.append(int("".join(j)))
        
    num_list = set(num_list) # 중복과 0, 1 제외
    if 0 in num_list :
        num_list.remove(0)        
    if 1 in num_list :
        num_list.remove(1)
        
    # 소수 판별 
    answer = len(num_list) # 모든 수가 소수라 가정하고 시작
    for i in num_list :
        if i != 2 :
            for j in range(2,int(i**0.5)+1) :
                if i % j== 0 :
                    answer -=1
                    break
        
    return answer

 

 

+ itertools.permutations 사용안한 다른사람 코드

 

# 0으로 시작하는 숫자. 
# 모든 숫자의 조합.
 
def isPrimeNumber(number):
    if number <= 1:
        return False
    else:
        for i in range(2, number // 2 + 1):
            if number % i == 0:
                return False
        return True
 
def getAllCombination(numbers, numList, leftCipher):
    '''
    numbers : 총 숫자카드 list
    numList : 가능한 숫자 배열 list
    leftCipher : 남은 자릿수
    '''
 
    # 현재 가능한 숫자 배열 list를 기준으로 추가가 가능한 숫자들은 찾는다. 
    newNumList = [[]]
    for li in numList:
        for i in numbers:
            if i in li and li.count(i) <= numbers.count(i) - 1:
                tmp = li[:]
                tmp.append(i)
                newNumList.append(tmp)
            if i not in li:
                tmp = li[:]
                tmp.append(i)
                newNumList.append(tmp)
 
    leftCipher -= 1
 
    if leftCipher == 0:
        return newNumList
    else:
        return getAllCombination(numbers, newNumList, leftCipher)
 
def removeFirstZero(numList):
    for i, num in enumerate(numList):
        firstNumIsZero = bool()
 
        while True:
            if len(num) >= 2 and num[0] == '0':
                firstNumIsZero = True
            else:
                numList[i] = num
                break
 
            num = num[1:]
 
def getUnique2DList(numList):
    for i, val in enumerate(numList):
        tmp = str()
        for char in val:
            tmp += char
        numList[i] = tmp
 
    newList = list(set(numList))
    return newList
 
def solution(numbers):    
    availableAnswer = getAllCombination(numbers, [[]], len(numbers))
    del availableAnswer[0]
    removeFirstZero(availableAnswer)
    availableAnswer = getUnique2DList(availableAnswer)
 
    answer = 0
    for val in availableAnswer:
        if isPrimeNumber(int(val)):
            print(val)
            answer += 1
 
    return answer