문제: https://school.programmers.co.kr/learn/courses/30/lessons/42839
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이 (간단하게)
- 소수인지 검증하는 함수 생성
- 이를 검증할 때 모든 수를 탐색하는 게 아니라, 제곱근까지만 탐색하면 된다.
- 에라토스테네스의 체를 이용해도 좋다.
- 문자열을 받아서 1자리부터 ~ 문자열 길이만큼의 순열 집합을 생성한다.
- 이 집합을 위에 정의한 함수를 가지고 소수인지 아닌지 검증한다
- 소수인 부분만 answer 배열에 저장한다
- 중복되는 부분을 제거하고 결과 값을 반환한다.
풀이 (자세하게)
소수 검증 함수 선언
def check(n):
if n < 2:
return False
for i in range(2, int(n**(1/2))+1):
if n % i == 0:
return False
return True제곱근 판정을 이용하면 된다.
제곱근 판정
- 1보다 큰 임의의 정수 a에 대해, 만일 a가 root(a) 보다 작은 소수에 의해 나누어지지 않으면 소수이다.
이를 증명하는 방법도 있지만, 이는 코딩테스트 풀이할 때 이용하지 않으므로 생략하겠다.
*20240502 추가
왜 제곱근까지만 확인하면 충분한가?
- 약수의 쌍: 수 이 소수가 아닌 경우, 형태로 표현할 수 있다(여기서 와 는 의 약수). 만약 와 둘 다 의 제곱근보다 크다면, 는 보다 커지므로 불가능하다. 따라서 적어도 하나의 약수는 의 제곱근 이하다.
- 효율성 증가: 의 제곱근까지만 확인하면 약수가 있는지 없는지를 더 빠르게 판단할 수 있다. 예를 들어, 이라면, 100의 제곱근은 10이므로, 단지 2부터 10까지만 검사하면 된다. 만약 10까지 약수가 없다면, 11부터 99까지 어떤 수로도 100을 나누어 떨어뜨릴 수 없다는 것이 자명해진다.
문자열 받아서 순열로 처리
def solution(numbers):
answer = set()
arr = []
for i in range(1, len(numbers)+1):
arr+= list(permutations(numbers, i))중복을 제거하기 위해서 후처리 하는 방법도 있지만, 필자는 처음부터 반환할 answer를 집합형으로 생성해 중복을 허용하지 않았다.
이후 순열로 처리하기 위해서 itertools 라이브러리의 permutations 메서드를 사용했다.
permutations 메서드는 순열로 만들 iterable 한 객체와 몇 자리 순열로 만들지에 대한 숫자로 이루어져 있다.
문제를 풀기 위해선 1자리부터~문자열의 크기만큼의 순열이 필요하므로 이를 반복문으로 처리하였다.
문자열을 정수형으로 변환
num = [int(''.join(x)) for x in arr]join 메서드를 통해서 str형을 int형으로 변환해서 새로운 배열에 저장하였다.
각 집합 원소들 검증
for i in num:
if check(i):
answer.add(i)반복문을 통해서 순열 집합으로 이루어진 배열의 원소들을 반복문을 통해 검증하였다.
전체 코드
from itertools import permutations
def check(n):
if n < 2:
return False
for i in range(2, int(n**(1/2))+1):
if n % i == 0:
return False
return True
def solution(numbers):
answer = set()
arr = []
for i in range(1, len(numbers)+1):
arr+= list(permutations(numbers, i))
num = [int(''.join(x)) for x in arr]
for i in num:
if check(i):
answer.add(i)
return len(answer)