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

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

코딩테스트 연습 - 소수 찾기

1차 시도

모든  조합을 만들고 소수만 남겨야겠다고 생각했다.

조합은 만들려는 중 순열 조합?이런건 난 다 까먹어서 아래 N으로 표현에서 노가다 한 방법대로 했다.

https://eunsera.tistory.com/24?category=1046251 

[프로그래머스] [Python] Level3_N으로 표현

그랬더니 한 숫자는 한번씩만 들어가야하는데 중복해서 들어가고...암튼 난리남

그리고 소수 걸러내는 것도 제곱근 구해서 하는거 처음 알았음 (문송합니다...)

from itertools import permutations
def solution(numbers):
    arr = list(numbers)
    p_list = []
    ans = 0
    
    for i in range(1,len(arr)+1):
        npr = permutations(arr, i)
        for p in npr:
            s = '' 
            for j in list(p) : s+=j
            p_list.append(int(s))
    p_list = list(set(p_list))
    
    for p in p_list:
        flag = True
        tmp = 2
        #0,1은 미리 제외
        if p==0 or p==1: flag = False
        #소수인지아닌지
        while(tmp<p): 
            if p%tmp ==0: #소수아님
                flag = False
                break
            else:
                tmp+=1
        if(flag): #소수
            ans += 1
    return ans

2차 시도

남들 다 하는대로 얌전하게 permutation을 쓰기로 했다.

 

소수인지 검사하는 부분에서 if문 처음 걸러낼 때, 음 소수아닌거 다 걸러면 되나?!

그럼 2의 배수 다빼자!!!하고 p%2 == 0도 넣었었는데

이렇게 되면 2도 소수인데 걸러져버려서 테스트케이스 4개 정도 정확성 fail이 떴었다

 

from itertools import permutations

def solution(numbers):
    answer = []
    nums = [n for n in numbers]
    per = []
    
    for i in range(1,len(numbers)+1):
        per += list(permutations(nums, i)) #순열조합
    per = set([int(("").join(p)) for p in per])
    
    for p in per:#소수인지 검사
        if p==0 or p==1 :
            continue
        flag = True #소수맞음
        for i in range(2,int(p**0.5)+1):
            if p%i == 0:
                flag = False #소수아님
                break
        if flag : answer.append(p)
    
    return len(answer)

 

from itertools import permutations

def solution(numbers):
    answer = []                                   
    nums = [n for n in numbers]                   # numbers를 하나씩 자른 것
    per = []                                      
    for i in range(1, len(numbers)+1):            # numbers의 각 숫자들을 순열로 모든 경우 만들기
        per += list(permutations(nums, i))        # i개씩 순열조합
    new_nums = [int(("").join(p)) for p in per]   # 각 순열조합을 하나의 int형 숫자로 변환

    for n in new_nums:                            # 모든 int형 숫자에 대해 소수인지 판별
        if n < 2:                                 # 2보다 작은 1,0의 경우 소수 아님
            continue
        check = True            
        for i in range(2,int(n**0.5) + 1):        # n의 제곱근 보다 작은 숫자까지만 나눗셈
            if n % i == 0:                        # 하나라도 나눠떨어진다면 소수 아님!
                check = False
                break
        if check:
            answer.append(n)                      # 소수일경우 answer 배열에 추가
    print(new_nums)
    return len(set(answer))

💡최종로직

0. numbers를 문자열이 아니라 떨어진 숫자 list로 바꾼다

1. 숫자 list를 돌면서 permutation 실행

2. permutation한걸 다시 숫자로 변환하면서 set으로 바꿔 중복 제거

3. 숫자로 변환한 list를 돌면서

  3-1. 0이거나 1이면 out

  3-2. 해당 수의 제곱근까지 순회하며 나눴을 때 나머지가 0이게 하는 숫자(인수)가 있으면 out

  3-3. out일때 flag = False하는데 여기서 살아남은 애들만 answer list에 appen

4. answer의 길이 return

 

permutation 공부가 필요

사실 permutation이 포함된 itertools 라이브러리를 봐야할 것같다

---

2021.09.29

 

from itertools import permutations
def solution(numbers):
    arr = list(numbers)
    p_list = []
    ans = 0
    
    for i in range(1,len(arr)+1):
        npr = permutations(arr, i)
        for p in npr:
            s = '' 
            for j in list(p) : s+=j
            p_list.append(int(s))
    p_list = list(set(p_list))
    
    for p in p_list:
        flag = True
        tmp = 2
        #0,1은 미리 제외
        if p==0 or p==1: flag = False
        #소수인지아닌지
        while(tmp<p): 
            if p%tmp ==0: #소수아님
                flag = False
                break
            else:
                tmp+=1
        if(flag): #소수
            ans += 1
    return ans

 

오늘은 아무것도 안보고 혼자 풀었다!

중간에 시간이 좀 걸린 부분은  append할 때 바로 int로 하면 되는데 string으로 받았다가 '011', '11' 같은 게 중복으로 들어가서 set에서 제거가 덜 되었다.

int로 형변환해서 list에 넣으니 중복제거도 잘되고 나중에 형변환도 안해도 돼서 편했다.

 

소수 판별 로직은 Flag를 하나 선언해서 true로 시작한 다음, 소수가 아닌 로직에 거릴 때 마다 flag를 false로 바꿔주면서 break를 걸어서 빠져나온다.

  1. 0과 1은 소수가 아니다

  2. 자신보다 작은 수 중에 나머지 연산 %의 결과가 0이면, 나누어 떨어졌다는 뜻이니 소수가 아니다.

위 2가지를 걸려져서 while문을 빠져나온 수는 소수이므로 flag값이 true이면 소수이다.