문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한 사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예제
| numbers | return |
|---|---|
| "17" | 3 |
| "011" | 2 |
소수 판별하기를 한참전에 풀었던 기억이 있어서 문자열을 숫자로 변환한 뒤, 여러 조합들만 조건으로 걸러서 소수 판별하면 어렵지 않을 것이라고 생각했다..결과는 마음처럼 안나왔고, 시간을 엄청 쏟았다..🥲
코드 작성
1. 첫 번째 시도
from itertools import permutations
def isPrime(list_num):
cnt=0
for num in list_num:
flag=True
for i in range(3,num//2+1,2):
if num%i==0:
flag=False
continue
if flag:
cnt+=1
return cnt
def solution(numbers):
lst=list(numbers)
temp_num=[]
list_num=[]
for i in range(1,len(lst)+1):
num_list=list(permutations(lst,i))
set_num=[]
for temp_lst in num_list:
set_num.append(int(''.join(temp_lst)))
temp_num.append(list(set(set_num)))
for el in temp_num:
for i in range(len(el)):
if el[i]==2:
list_num.append(el[i])
elif el[i]<2 or el[i] in list_num or el[i]%2==0:
continue
else:
list_num.append(el[i])
return isPrime(list_num)우선 permutations 모듈을 사용해서 만들어질 수 있는 모든 수의 경우를 만들었고, 그걸 set_num이라는 리스트에 넣은 후, 다시 set으로 변환하여 중복된 숫자를 없애려고 했다. 그후 중복을 거른 리스트를 가지고 2(짝수 중 유일한 소수)와 그 외의 1을 제외한 홀수들만 소수인지 판별하기 위해 isPrime함수로 전달하는 방식이었다. 뭔가 찝찝하지만 테스트 코드를 다양하게 넣어도 다 통과되길래 될런가 싶었는데,,
결과
실패,,
이후에도 계속해서 코드를 조금씩 수정해나갔는데 테스트1과 10의 벽을 넘을 수 없었다..고민을 거듭하면서 기존의 코드에 크게 두 가지의 문제점이 있다는 것을 알게됐다.
1. isPrime() 함수의 쓰임
isPrime() 함수는 소수임을 판별하는 기능을 하므로 굳이 temp_num에서 하나씩 element로 빼면서 미리 2인지, 1을 제외한 홀수인지 등을 검증하지 않아도 된다고 생각한다. 어차피 위에서 한번 조건문으로 거르지 않아도 소수를 검증하는 곳이 isPrime() 함수이니까 한꺼번에 검증하는데 효율적일 것이다.
2. 중복 처리의 불필요한 복잡성
list에 넣은 요소들을 set()을 사용하여 중복을 제거하고 나서 다시 list로 변환하는 것이 비효율적이다. 이 부분은 스스로 짜면서도 이게 맞나 싶었던 부분이다. 리스트의 중복 처리에 대한 궁금증이 아래 두 번째로 시도한 코드와 같이 코드를 짜면서 해소되었다.
2. 두 번째 시도
from itertools import permutations
def isPrime(num):
if num==2:
return True
if num<2:
return False
if num%2==0:
return False
for i in range(3,num//2+1,2):
if num%i==0:
return False
return True
def solution(numbers):
lst=list(numbers)
temp_num=[]
list_num=[]
for i in range(1,len(lst)+1):
num_list=list(permutations(lst,i))
for temp_lst in num_list:
num=int(''.join(temp_lst))
if num not in temp_num:
temp_num.append(num)
if isPrime(num):
list_num.append(num)
return len(list_num) 위와 같은 문제점을 해결하고자 코드를 개선했다. 소수인지 검증하는 동작은 isPrime()함수에서만 동작하도록 했고, 소수이면 True 아니면 False가 반환되도록 했다. 또한, list와 set반복의 향연으로 중복 처리를 했던 이전과 다르게 temp_num이라는 리스트에 이미 존재하면 num을 넣지 않고, 없으면 새로 추가하는 식으로 하여 그 안에 들어간 num만 isPrime()함수로 전달되게끔 했다. 결과적으로 소수이면 list_num이라는 리스트에 해당 소수가 들어가게 되고, 최종 return을 할 때, 리스트의 길이를 반환하는 방식으로 로직을 짰다.
결과
해결!
🔥 잊지말자!
1. 함수나 기능을 구현할 때 필요한 기능이나 목적을 명확히 이해하고 구현해야 한다한다! 소수 판별에 관련한 처리는 모두 isPrime()에서 하기.
2. list 중복 처리를 할 수 있는 또다른 방법을 배웠다. 앞으로도 유용하게 사용할 예정이다!!
