https://school.programmers.co.kr/learn/courses/30/lessons/42839
문제 정의
문자열로 주어진 종이조각으로 만들 수 있는 소수가 몇 개인지 계산해야한다.
접근 방법
문자열로 주어진 종이조각을 분리한 후 조합을 이용해 만들 수 있는 모든 숫자를 만든다.
그 다음에 그 숫자가 소수인지 판단하면 된다.
이 때 쓸 수 있는 유용한 함수에는 itertools의 permutations이 있다.
문제 해설
- permutations의 인자로 들어갈 리스트를 만들어 주기 위해서 numbers를 분리했다. (numbers는 문자열로, 공백이 없이 주어졌기에 split() 함수를 사용할 수 없었다. 따라서 for문으로 일일히 분리했다.)
- permutations을 사용해 모든 조합을 구하고 join 함수를 사용해서 다시 정수를 만들어준다.
- 만들어진 숫자가 소수인지 판단한다.
풀이
- 처음시도: 시간초과
- 이유: 소수인지 판단하는 구간에서 1~n 까지 다 나눴는데, 여기서 숫자가 큰 경우 시간 초과가 난다. 사실 소수는 자기자신 외의 나눠지는 정수가 하나만 있어도 소수가 되지 않으므로, 전체 다 비교할 필요가 없다. 그래서 소수를 판단하는 함수를 최대한 효율적이게 짜서 다시 구현했다.
from itertools import permutations
def solution(numbers):
answer = 0
n_list = [numbers[i] for i in range(len(numbers))] # 흩어진 종이조각 리스트
perms = [] # 종이 조각으로 만들 수 있는 소수 조각 리스트
for i in range(1, len(n_list)+1):
perm = permutations(n_list, i)
for p in perm:
n = int(''.join(p)) # 만들어진 조합 정수
cnt = 0 # 약수의 개수
# 소수 인지 판단하기
for j in range(1, n+1):
if n % j == 0:
cnt += 1
if cnt == 2:
perms.append(n)
answer = len(set(perms))
return answer
- 성공한 코드
from itertools import permutations
#소수 판별 함수
def is_prime_number(x) :
if x < 2 :
return False
for i in range(2, x) :
if x % i == 0 :
return False
return True
def solution(numbers):
answer = 0
n_list = [numbers[i] for i in range(len(numbers))] # 흩어진 종이조각 리스트
perms = [] # 종이 조각으로 만들 수 있는 소수 조각 리스트
for i in range(1, len(n_list)+1):
perm = permutations(n_list, i)
for p in perm:
n = int(''.join(p)) # 만들어진 조합 정수
# 소수 인지 판단하기
if is_prime_number(n):
perms.append(n)
answer = len(set(perms))
return answer
꿀팁
num.append(list(set(map(''.join, permutations(numbers, i)))))- permutations에 바로 map함수와 join을 사용해 문자열을 바로 합칠 수 있다.
per = list(set(map(int, set(sum(num, []))))- 리스트 안의 리스트를 합치고 싶을 땐,
sum(list, [])처럼 빈 리스트와 함께 합쳐주면 하나의 리스트로 합쳐진다.
정리
- 만들 수 있는 모든 숫자가 소수인지 판단하는 ‘완전탐색’ 문제이다.
- 아이디어를 떠올리기 쉬운 문제였지만, 중간중간 실수가 많아서 한번에 정답을 맞추진 못했다.
- 첫번째로,
int(’’.join(p))부분에서, string에 int 변환이 안된다는 오류를 만났는데, 알고보니permutations을 1이 아닌 0 부터 시작해서 빈 리스트가 만들어지면서 int 변환에 예외가 있었다. 형 변환이 안된다면 꼭 변환할 수 있는 형태인지 파악하도록 하자.
- 두번째로, 소수를 판단하는 부분이다. 위에서 말했듯이 소수를 판단하는데 1~n까지 체크할 필요는 없다. 따라서 저 위의 함수를 잘 외우면 나중에 유용할 것 같다.
Uploaded by N2T
