[고득점 Kit / 완전탐색] 소수찾기

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

프로그래머스

 

이 문제는 다음과 같은 흐름으로 풀었다.

 

1. numbers로 만들어질 수 있는 모든 숫자 조합을 구한다.

2. 구한 숫자 중 소수인지 아닌지 판별한다

 

from itertools import permutations

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

def solution(numbers):
    possible_numbers = set()  # 중복 제거를 위한 set
    
    # numbers에서 나올 수 있는 모든 조합을 확인
    for length in range(1, len(numbers) + 1):
        # permutations를 이용해 숫자의 모든 순열을 생성
        for p in permutations(numbers, length):
            num = int(''.join(p))  # 순열로 만들어진 튜플을 문자열로 합친 뒤 숫자로 변환
            possible_numbers.add(num)  # set에 추가
    
    # 소수 판별 및 카운트
    prime_count = 0
    for num in possible_numbers:
        if is_prime(num):
            prime_count += 1
    
    return prime_count

 

 

소수 판별은 워낙 유명한 내용이니 순열을 이용해 숫자의 조합을 구하는 부분을 자세히 보자.

 

for length in range(1, len(numbers) + 1):
    for p in permutations(numbers, length):
        num = int(''.join(p))
        possible_numbers.add(num)

 

1. range(1, len(numbers) + 1):

• numbers는 입력으로 주어지는 숫자 문자열이다. 예를 들어 "17"이면, numbers는 '1', '7'이라는 문자들로 이루어져 있다.
• range(1, len(numbers) + 1)은 숫자 길이가 1개부터 numbers의 길이(여기서는 2)까지의 모든 경우를 고려하기 위해서 사용한다.
  • 예를 들어, "17"에서 숫자의 길이가 1인 경우와 2인 경우 모두를 다룬다.
  • 만약 numbers = "17"이면, length는 1 또는 2가 된다.

2. permutations(numbers, length):

• permutations는 순열을 생성하는 함수다. 즉, 주어진 문자들을 다양한 순서로 배열하는 모든 가능한 조합을 찾아낸다.
  • permutations(numbers, length)는 numbers에서 주어진 길이만큼의 순서를 고려한 순열을 생성한다.
  • 예를 들어, "17"이라는 문자열이 주어졌고, length = 1이면 가능한 순열은 '1', '7'이다.
  • length = 2이면 가능한 순열은 '17', '71'이다.

3. num = int(''.join(p)):

• p는 permutations가 반환하는 하나의 순열 튜플이다. 예를 들어, p가 ('1', '7')이면 이는 문자 '1'과 '7'으로 구성된 순열이다.
• ''.join(p)는 순열에 있는 문자들을 하나의 문자열로 합치는 과정이다. 예를 들어, p = ('1', '7')이면 ''.join(p)는 '17'이 된다.
• int(''.join(p))는 이렇게 합쳐진 문자열을 숫자로 변환하는 과정이다. 즉, 문자열 '17'을 정수 17로 변환한다.

4. possible_numbers.add(num):

• possible_numbers는 집합(set)이다. 집합은 중복된 값을 허용하지 않기 때문에, 중복된 숫자가 생성되어도 한 번만 저장된다.
• 앞에서 만든 숫자 num을 집합에 추가한다. 이 과정을 통해 모든 가능한 숫자 조합을 모으게 된다.

 

테스트케이스로 이해해보자.

 

만약 numbers = "011"이라면, 이 코드 부분은 다음과 같이 작동한다.

1. length = 1일 때:
   • 가능한 순열: '0', '1', '1'
   • 숫자로 변환: 0, 1, 1 → 집합에 저장: {0, 1}
2. length = 2일 때:
   • 가능한 순열: '01', '10', '11'
   • 숫자로 변환: 1, 10, 11 → 집합에 저장: {0, 1, 10, 11}
3. length = 3일 때:
   • 가능한 순열: '011', '101', '110'
   • 숫자로 변환: 11, 101, 110 → 집합에 저장: {0, 1, 10, 11, 101, 110}