[ 프로그래머스 ] 소수 찾기

/  제출 1  /

def isPrime(x):
    x = int(x)
    if x == 0 or x == 1:
        return False
    for i in range(2,x):
        if x%i == 0:
            return False
    return True

def solution(numbers):
    answer = []
    cand_num = ''
    for i in range(len(numbers)):
        cand_num = numbers[i]
        if isPrime(cand_num)and int(cand_num) not in answer:
            answer.append(int(cand_num))
        for j in range(len(numbers)):
            if i != j:
                cand_num += numbers[j]
                if isPrime(cand_num)and int(cand_num) not in answer:
                    answer.append(int(cand_num))
            
    print(answer)
    return len(answer)

채점 결과

정확성: 33.3

합계: 33.3 / 100.0

1,2,4,7,9,10,11,12 실패

 

어우 처참한 성적..

뭐 단단히 꼬인 것 같은데 다시 봅시다..

 

/  디버깅  /

어디서 문제가 나온 지 알겠습니다. 소수인지 판별하기 전에 숫자를 뽑는 모집 값을 너무 적게 잡았습니다.

for문 2번으로 값들을 생성하는데, 순서가 고정된 채로 해서

예를들어 1231이 쪽지로 주어진 것이라면 2131 이나 3121은 나오지만 3112, 3211 등은 만들어지지 않고 있습니다.

해서 숫자들끼리 섞어 소수인지 판별할 수들을 정확히 만들도록 로직을 다시 구성했습니다.

 

---

/  제출 2  /

from itertools import permutations
def isPrime(x):
    if x == 0 or x == 1:
        return False
    for i in range(2,x):
        if x%i == 0:
            return False
    return True

def solution(numbers):
    answer = []
    for i in range(1,len(numbers)+1):
        x = ''
        candidate = list(permutations(numbers,i))
        for j in range(len(candidate)):
            x = ''
            for k in range(len(candidate[j])):
                x += candidate[j][k]
            x = int(x)
            if isPrime(x) and x not in answer:
                answer.append(x)
    print(answer)
    return len(answer)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

 

흐 ... 해당 문제를 찾아서 풀었습니다. 후보군 잡는건 permutations함수를 사용해서 모든 집단을 찾아서 풀었습니다.

전체 풀이까지 40분 걸렸네요. 시간을 더 줄여나가야할텐데.. 일단 뭐가 문제인지 찾을 수 있게 되었다는 것에서 의의를 가집니다. 

 

다만, 효율성 평가까지 하면 위의 코드가 정상적으로 좋은 점수를 받을 수 있을 수 없을 것 같습니다. 

소수 판별에서도 빠른 속도로 동작하지 않을 것 같고 정말 완전 탐색처럼 모든 옵션을 다 검사한 느낌 같습니다.

다른 분들 코드 보면서 발전 여지를 확인해 봅시다.

 

소수 판별

https://53perc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0

(파이썬) 소수 판별하기

 

---

 

/  다른 분들 풀이  /

 

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

소수 구하는 함수를 최적화한 코드를 제출하셨습니다. 딱 제가 원하던 소수 판별 함수의 성능 최적화 버전인 것 같습니다.

덕분에 에라토스테네스의 체 알고리즘도 익히고 갈 수 있었습니다.

 

primeSet = set()


def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False

    return True


def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])


def solution(numbers):
    makeCombinations("", numbers)

    answer = len(primeSet)

    return answer

해당 코드는 permutations를 안 쓰고 후보집단을 만들어보고 싶었던 제 욕심을 충족시켜줬습니다.

 

진짜 똑똑하신 분들 참 많고 덕분에 많이 배웁니다.