[완전탐색] 프로그래머스 level 2 소수찾기 (Python 파이썬)

💡문제 링크

https://school.programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

 

 

💡문제 분석 요약

이것도 진짜 뭔 기법 이런 게 아니라 그냥 빡 구현

숫자카드를 뽑은 뒤, 그 숫자카드로 만들 수 있는 소수를 만드는 문제이다.

숫자카드는 numbers라는 변수로, 문자열 형태로 주어진다.

 

💡알고리즘 설계

1. numbers 문자열을 리스트로 만든다.

예. "123" -> [1, 2, 3]

2. 순열을 이용해서 만들 수 있는 모든 경우의 수를 만든다.

3. 중복은 제거한다.

4. 소수 여부를 확인한다.(0과 1은 당연히 제거)

💡코드

from itertools import permutations

def solution(numbers):
    # numbers를 리스트로 만든다.
    num_list = [i for i in numbers] 
    
    # 만들 수 있는 모든 경우의 수를 만든다.
    can_list = []
    for n in range(1, len(num_list) + 1):
        for c in permutations(num_list, n):
            can_list.append(int(''.join(c))) 
    # 중복을 제거한다.
    can_list = sorted(list(set(can_list)))
    print(can_list)
    if 0 in can_list:
        can_list.remove(0)
    if 1 in can_list:
        can_list.remove(1)
    # 소수 여부를 확인한다.      
    for c in can_list[:]:
        for i in range(2, c):
            if c % i == 0:
                can_list.remove(c)
                break
    return len(can_list)

 

💡 오답 풀이

...

 

💡 다른 풀이

문자열을 리스트로 만들기

그냥 list(문자열)하면 끝!

n = list(numbers)

소수 판별 함수

나는 반복문의 범위가 range(2, c)였는데, 다른 풀이를 보니 굳이 c-1까지 반복할 필요 없이 range(2, int(c**0.5) + 1)로 int(c**0.5)까지만 반복하면 된다.

def is_prime(x):    #소수 판별 함수
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

모든 경우의 수 반환 함수

리스트에 리스트를 더할 수도 있었지!!!

a = []
for i in range(1, len(n)+1):
        a += list(permutations(n, i))   #경우의 수 반환

 

다른 풀이를 참고해서 새로 짠 코드

from itertools import permutations

def is_prime(x):
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    # numbers를 리스트로 만든다.
    num_list = list(numbers)
    
    # 만들 수 있는 모든 경우의 수를 만든다.
    can_list = []
    for i in range(1, len(num_list) + 1):
        can_list += list(permutations(num_list, i))
    can_list = [int(''.join(c)) for c in can_list]
    # 중복을 제거한다.
    can_list = sorted(list(set(can_list)))

    # 소수 여부를 확인한다.      
    for c in can_list:
        if c <= 1:
            continue
        elif is_prime(c):
            answer += 1
            
    return answer

💡 느낀점 or 기억할정보

1. permutations(리스트, 숫자)를 바로 쓰면 안 되고, for문을 돌려서 써야 한다.

2. permutations는 결과가 튜플 형태로 나오는데, 이거를 문자열로 변환하려면 ''.join(튜플)을 해줘야 한다.

3. 중복을 제거한 뒤 정렬하려면 sorted(list(set(리스트)))를 해서 3중 함수를 사용해준다.

4. 파이썬에서 특정 원소를 제거하는 건 delete가 아니라 remove!!! 자꾸 헷갈린다

5. 소수 여부를 확인하는 반복문에서 for c in car_list가 아니라 car_list[:]라고 하는 이유: 반복문 안에 remove 함수가 있어서, for c in car_list를 안하면 원래 리스트가 바뀐다. 그래서 반복문이 이상하게 돌아간다.. 꼭 car_list[:]로 중복된 리스트 사용하기!