프로그래머스 - 코딩테스트 고득점 Kit - 완전탐색 - 소수 찾기 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/42839

일단 문제 설명은 위 링크를 참고하시면 됩니다.

 

문제를 이해하셨다는 전제하에 문제를 해결한 코드를 설명하도록 하겠습니다.

 

생각한 알고리즘

 

1. 'numbers'에 있는 원소에 대한 모든 조합 찾기(+ 이러한 조합들을 정수 형태로 저장)

1) itertools.permutations(numbers, 원소크기) 사용(numbers 안의 원소들을 이용하여 원소크기로 구성된 조합들을 출력)

일단 이 함수를 이용하기 위해 import itertools 를 해줘야한다.

이 함수에 대해 예시를 통해 설명하자면

예) numbers='0123'인 경우, i+1개의 원소를 뽑아 조합해라. ( list(itertools.permutations(numbers, i+1)) )

i+1 = 2인 경우, 아래와 같이 조합이 되고, 분홍색으로 표시한 코드를 print하면 아래와 같이 저장된다.

[(0,1), (0,2), (0,3), (1,0), (2,0), (3,0), (1,2), (1,3), (2,1), (3,1), (2,3), (3,2)]

 

각 원소가 tuple 형태로 저장이 된 것이다. 근데 우리는 이 상태로는 절대로 문제를 풀 수 없기 때문에 

 

2) map(lambda x: int(''.join(list(x))), temp)를 이용하였다.

일단 1-1)의 값이 temp에 저장이 되었고, 만약 연한 노란색으로 표시한 코드를 이용하면

내가 추구한 값인 정수형태로 저장이 된다. 

 

일단 int(''.join(list(x))) 서 변환이 아래와 같은 순서로 3번 일어난다.

 

a. tuple 형태였던 원소가 list형태로 변한다. 

예) [(0,1), (0,2), ...... , (3,1), (2,3), (3,2)] => [[0,1], [0,2], ...... , [3,1], [2,3], [3,2]] 

 

b. 각 원소가 문자열로 바뀐다.

예) [[0,1], [0,2], ...... , [3,1], [2,3], [3,2]]  => ['01', '02', ...... , '31', '23', '32'] 

 

c. 각 원소가 정수형태로 바뀐다.

예) ['01', '02', ...... , '31', '23', '32']  => [1, 2, ...... , 31, 23, 32] 

 

3) set을 이용하여 중복된 값을 없애고 list형태로 printList를 저장했다.

 

2. printList에 있는 원소들 중 소수 개수 찾기

일단 소수값 중 유일한 짝수는 2이고 나머지는 다 홀수이다.

1) 원소가 2인 경우(소수), 2) 원소가 2의 배수인 경우 또는 2보다 작은 경우(합성수)에 해당하는지 확인한 후 없다면

4) (원소 / 홀수값)의 나머지가 0인 경우(합성수), check에 False를 저장시키고,

만약 합성수가 아니라면 check가 True로 유지되어 answer을 1 더한다.

 

import itertools
def solution(numbers):
    answer = 0
    printList=[]
    #1
    for i in range(len(numbers)):
        temp = list(itertools.permutations(numbers, i+1)) #1-1)
        tmp = map(lambda x: int(''.join(list(x))), temp) #1-2)
        lst = list(tmp)
        printList = printList + lst
    
    printList = list(set(printList)) #1-3)
    
    
    for i in printList:
        if i==2:
            answer+=1
            continue
        elif i<2 or i%2==0:
            continue
        check=True
        for j in range(3,i,2):
            if i%j==0:
                check=False
                break
        if check:
            answer+=1
    return answer