99클럽(2기) 코테 스터디 3일차 TIL # 완전탐색

프로그래머스 - 소수 찾기

• 문제: 한자리 숫자가 적힌 종이 조각이 흩어져 있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어질 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 반환하도록 solution 함수를 완성해주세요.
• 제한 사항:
  • numbers는 길이 1 이상 7 이하인 문자열입니다.
  • numbers는 0~9까지 숫자만으로 이루어져 있습니다.
  • "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

---

1. 나의 풀이

 문제 풀이에 앞서 문제를 어떻게 풀지 정리해보자면, numbers 문자열을 재배치할 수 있는 모든 경우의 수에서 소수가 몇 개인지 확인하면 된다. 소수 판별함수를 따로 만들면 좋을 것 같다.

 

1) 소수 판별 함수 만들기

 소수의 정의는 1보다 큰 자연수 중 1과 자기 자신만 약수로 가지는 수를 말한다. 특정 자연수 n이 소수라면 '2 ~ n'의 범위에서 나머지가 0으로 나누어떨어지는 약수가 없어야 한다. 그런데 사실 2부터 n까지 따질 필요 없이 n의 제곱근까지만 확인해보면 된다. n이 소수가 아니라면, n=a×b 형태로 쓸 수 있는데, a와 b 둘 중 하나는 반드시 n의 제곱근​ 이하이기 때문이다(출처). 따라서 소수를 판별할 때는 2부터 n의 제곱근​까지의 수로 나누어 떨어지는지 확인하면 충분하다.

 

2) numbers로 순열 만들기(numbers를 재배치할 수 있는 모든 경우의 수)

 numbers를 재배치할 수 있는 경우의 수를 구하는 것은 '순열' 문제이다. 파이썬에서는 itertools 모듈의 permutations 함수를 사용하면 순열을 손쉽게 구할 수 있다. 

 

• permutations 사용법
  • permutations(iterable, r): 반복 가능한 객체에서 r개의 원소로 구성된 순열 반환

 그런데 numbers는 모든 종이 조각을 합쳐놓은 것이고, 순열의 경우의 수는 하나의 조각으로 만드는 경우부터 모든 조각으로 만드는 경우까지 따져봐야 한다. 예를 들어, numbers의 길이가 n이라면 하나의 조각으로 순열을 만드는 경우의 수 + 두 개의 조각으로 순열을 만드는 경우의 수 + ... n개의 조각으로 순열을 만드는 경우의 수 모두를 고려해야 한다는 뜻이다.

 

3) 생성된 각 순열이 소수인지 확인하기

  앞서 만든 순열이 소수인지 확인하는 과정을 거친다. 

from itertools import permutations

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num ** 0.5) + 1): # 제곱근은 정수가 아닐 수 있으므로 range 함수에서의 사용을 위해 int 형변환을 해준다
        if num % i == 0:
            return False
    return True

def solution(numbers):
    nums = [] # numbers를 구성하는 문자열 하나하나를 저장하는 리스트
    permutations = [] # nums에 대한 순열을 저장하는 리스트
    answer = 0 # answer 초기화

    for num in numbers:
        nums.append(num)

    for i in range(1, len(nums) + 1):
    	permutations += list(permutations(nums, i)) # 1개의 조각으로 만들 수 있는 순열부터 최대 조각으로 만들 수 있는 모든 순열을 permutations에 추가
    permutations = list(set(int("".join(i)) for i in all_nums)) # 

    for i in permutations:
        if is_prime(i):
            answer += 1
    return answer

 

2. 다른 사람의 풀이

 1개의 조각부터 numbers 길이 만큼의 조각 범위에서 순열을 만들어 주고 이를 세트 자료형에 더해준다. 여기에는 소수가 아닌 숫자가 포함되어 있으니 그 만큼의 개수를 제거해주는데, 특이한 점은 문제가 numbers로 구할 수 있는 소수의 '개수'를 구하는 것이기 때문에 굳이 소수가 무엇인지 구하지 않고 소수의 개수만 구했다는 것이다.

from itertools import permutations

def solution(numbers):
    a = set()
    for i in ragne(len(numbers)):
        a |= set(map(int, map("".join, permutations(list(numbers), 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)

3. 새롭게 알게 된 점 & 느낀점

• '|=' 복합 할당 연산자는 비트 OR 연산(|)과 할당(=)을 결합한 연산자이다. 한 번도 써본 적 없는데 다음에 set 자료형을 사용할 때 유용하게 쓸 것 같다.
• numbers를 구성하는 문자열을 굳이 하나씩 저장할 필요도, 소수가 무엇인지 구할 필요도 없었다. 구해야하는 답을 보고 조금 더 효율적인 풀이를 하는 연습을 해봐야겠다.