from itertools import permutations
def solution(numbers):
answer = []
num=[i for i in numbers]
p=[]
for i in range(1,len(numbers)+1):
p+=list(permutations(num, i))
res=[int(('').join(j)) for j in p]
res=set(res)
res=list(res)
print(res)
for i in res:
if i<2:
continue
check=True
for j in range(2, i):
if i%j==0: #소수 아님
check=False
break
if check:
answer.append(i)
return len(answer)
for i in numbers:
num.append(i)
num1=[i for i in numbers]
res=[]
for j in p:
res+=[int(''.join(j))]
res1=[int(''.join(j)) for j in p]
문제 접근이나 푸는 건 어렵지 않았지만, 쓰는 문법들을 잘 알아야 풀 수 있었다.
순열(permutations)를 사용하는 것과 .join을 쓰는 것이다.
res 배열에 값을 이어서 주고 싶다면 .join을 쓰게 되는데 이때 배열 변수에 넣는 것이기 때문에 밖에 []를 써야한다. 그렇지 않으면 배열에 값이 들어가지 않는다.
<소수 찾기 알고리즘>
[숫자 n 나누기]
1. 2부터 n-1까지 나누기def isPrime(n): for i in range(2, n): if n % i == 0: return False return True
n-1까지, n이 1과 자기 자신 외의 수로 나누어지는지 판단하는 알고리즘이다. 만약 나누어진다면 바로 false를 리턴한다. n-1까지 걸리지 않는다면 True가 리턴된다. 가장 간단하고, 기초적이지만 오래 걸린다. 2부터 n-1까지의 수 모두를 확인하기 때문에, 시간 복잡도가 O(n)이다.
- n/2까지 나누기
def isPrime(n): for i in range(2, n//2+1): if n % i == 0: return False return True
n의 모든 약수는 n/2보다 작다. 고로 2부터 n-1까지 확인할 필요가 없다는 뜻이다. 위 알고리즘보단 확인해야 할 조건이 반으로 줄었지만 여전히 시간 복잡도가 O(n)이기 때문에 느리다.
- n의 제곱급까지 나누기
def isPrime(n): for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True
n의 제곱근을 기준으로, 제곱근보다 작은 수들 중에 약수가 없다면, 제곱근보다 큰 수들은 n의 약수가 아니다. 예를 들어 n이 101이라면, √101+1까지의 수만 약수인지 확인해보면 된다. 만약 n/2 알고리즘을 쓰면 101//2+1 = 51, 즉 2~51까지 50번을 확인해야 하지만, n의 제곱근까지만 확인하면 √101+1 = 11, 즉 2~11까지 총 10번만 하면 된다. 그래서 시간 복잡도는 O(√n)으로, 1번의 방법들 중 제일 빠른 방법이다.
[에라토스테네스의 체]
def primeList(n): # n을 포함시키기 위함 n += 1 # [False(0), False(1), True(2), True(3), True(4) ... True(n)] sieve = [False, False] + [True] * (n) end = int(n**0.5) + 1 for i in range(2, end): if sieve[i] == True: for j in range(i+i, n, i): sieve[j] = False return [i for i in range(n) if sieve[i] == True]
sieve라는 0~n까지의 숫자가 소수라면 True, 아니면 False 값을 담고 있는 배열을 생성한다. 그리고 최대 약수인 √n을 종료 값으로 설정한 뒤, 만약 sieve[i]값이 참이라면(=소수라면) 그 값의 배수들을 모두 거짓(=소수가 아님)으로 바꾼다. 그리고 마지막에는 sieve의 값에 따라, 참이라면 return 배열에 i를 추가하는 방식으로 사용할 수 있다.
def primeList(n): a = [False,False] + [True]*(n-1) primes=[] end = int(n**0.5) + 1 for i in range(2, end): if a[i]: primes.append(i) for j in range(2*i, n, i): a[j] = False return primes
이런 식으로 사용해도 된다. list 대신 deque를 사용하면 시간 좀 더 단축된다.
설명 참고 사이트
그리고 문제를 풀면서 소수인 경우 배열에 값을 넣어줘야하는데 if else를 아래 코드와 같이 잘 못 사용하여서 오류를 많이 냈었다.
(처음 작성한 코드)
from itertools import permutations
def solution(numbers):
answer = []
num = []
for i in numbers:
num.append(i)
p=[]
for i in range(1,len(numbers)+1):
p+=list(permutations(num, i))
res=[]
for j in p:
res+=[int(''.join(j))]
res=set(res)
res=list(res)
# print(res)
for i in res:
if i<2:
continue
check=True
for j in range(2, i):
if i%j==0: #소수 아님
check=False
break
else:
answer.append(i)
break
# print(answer)
return len(answer)
이후 다른 사람의 코드를 참고하며 해석해서 잘못된 부분을 바로 잡을 수 있었다.