[프로그래머스/Level2/고득점키트] 소수 찾기 (C++)(Python)

[프로그래머스/Level2/고득점키트] 소수 찾기 (C++)(Python)

1. 문제

---

2. 접근/체크포인트

1. 주어진 문자열(numbers)로 만들 수 있는 모든 숫자 조합을 찾는다.
2. 가능한 모든 조합들에 대해 소수인지 판단하여, 소수일 경우 별도의 리스트에 분리.
3. 리스트에서 중복을 제거한 후 남은 갯수가 정답.

---

3. 해결 방법

1. 어떤 수가 소수인지 아닌지 판단하는 함수를 정의한다. (check_num)
2. 1부터 numbers의 길이(len(numbers))까지 조합수를 늘려가며 가능한 모든 조합을 찾는다.
   2-1. 1가지 숫자들의 조합, 2가지 숫자들의 조합, .... , len(numbers)가지 숫자들의 조합.
   2-2. 각 조합 단계마다 만들어진 리스트의 원소들을 join() 함수를 이용하여 합하고, 각 원소들을 int 형으로 변환한다.
   ex) join함수로 리스트의 원소(튜플)를 하나의 문자열로 합치는 과정
   1가지 숫자들의 조합으로 만들어진 리스트 = [('1',), ('2',), ('3',)] => ['1', '2', '3']
   2가지 숫자들의 조합으로 만들어진 리스트 = [('1','2'), ('2','3'), ('3','1')] =>[ ['12', '23', '31']
   2-3. 변환한 숫자를 check_num 함수를 이용하여 소수인지 판별한다.
3. 소수일 경우 tmp 리스트에 추가한다.
4. 최종 tmp 리스트를 set() 함수를 이용하여 집합으로 변환하여 중복을 제거한다.
5. 중복이 제거되고 남은 원소들의 갯수가 answer

---

4.전체코드

1. Python 코드

from itertools import permutations
import math


def check_num(num):
    
    if num < 2:
        return False
    else:
        # 2부터 해당수의 제곱근까지 나눠서 소수인지 확인 
        for i in range(2, int(math.sqrt(num))+1):
            if num%i == 0:
                return False
        return True


def solution(numbers):
    answer = 0
    tmp = []
    
    # numbers를 1개 ~ len(numbers)개까지 조합
    for i in range(1, len(numbers)+1):
        arr = list(permutations(numbers, i))
        for j in range (0, len(arr)):
            # i개를 조합시켜 생성된 리스트의 각 원소를 join후 int로 형변환
            num = int(''.join(arr[j]))
            # num이 소수 인지 확인, 소수이면 answer[]에 추가
            if check_num(num) :
                tmp.append(num)
    
    # answer리스트를 set(집합)으로 바꿔서 중복 제거 후 남은 갯수가 정답
    answer = len((set(tmp)))
        

    return answer

2. C++ 코드

추가 예정

---

5. 참고사항

👉 Python에서 순열을 구하는 방법, permutation() 함수

순열이란 : n개의 원소중에서 순서를 고려해 r개의 원소를 나열한 것.

📌 파이썬의 순열함수 사용법 : permutations(반복가능한 객체, 선택할 아이템의 수)

from itertools import permutations 
a = ['A','B','C']
per_list = permutations(a,2)  #리스트 a에서 순서 상관없이 2개 선택해서 조합
#결과 :  [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

👉 Python의 join(), split() 함수

1. split() 함수 : 문자열을 ()안의 구분자를 기준으로 분리하여 리스트로 반환하는 함수.

📌 split() 함수 사용법 : 문자열.split('구분자')

ex)

a = "2021-06-23"  
b = list(a.split('-')) 
#결과 : ["2021", "06", "23"]

2. join() 함수 : 리스트를 문자열로 합쳐주는 함수

📌 join() 함수 사용법 : '구분자'.join(리스트)

ex)

a = ['A', 'B', 'C']
b = list(''.join(a))   #구분자가 공백인 경우
c = list('_'.join(a))  #구분자가 _ 인 경우
#결과 b = "ABC" , c = "A_B_C"

---

6.다른 방법으로 풀어보기

추가 예정

---

7. 후기

순열, 조합 함수의 경우 자주 사용되기 때문에 사용법을 미리 익혀두자