728x90
1. 오늘의 문제
오늘 문제는 어제에 이어 완전탐색이었다.
숫자들을 쪼개서 하나씩 보는 것이니 하나의 글자를 노드로 생각하고 모든 노드를 돌면서 탐색해야 한다.
여기서도 재귀 함수의 냄새가 풀풀 났다.
더보기
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
2. 문제를 풀다가...
문제를 풀다가 2번과 10번에서 시간초과가 자꾸 걸렸다.
2부터 해당 값의 범위까지 range로 돌면서 나머지가 0인 것을 찾는 과정이 있었는데 이것을 모든 범위에서 실행했던 것.
어쨌든 간에 나머지가 0인 것이 하나만 나오더라도 소수가 아니기에 끝까지 계산할 필요가 없었다.
그래서 for문 중간에 break를 넣어 멈추게 하니 시간초과에 걸리지 않았다.
3. 코드
def solution(numbers):
numberLst = list(numbers)
answerLst = set()
def prime(num, lst):
if not lst:
return
for i, l in enumerate(lst):
numTemp = num
num = numTemp + l
lstCopy = lst.copy()
lstCopy.pop(i)
answerLst.add(int(num))
prime(num, lstCopy)
num = numTemp
prime("", numberLst)
total = 0
for a in answerLst:
if a == 1 or a == 0 :
continue
if a < 4:
total += 1
continue
div = 0
for k in range(2, a):
if a%k == 0:
div += 1
break
if div == 0:
total += 1
return total
4. 느낀점
재귀적 사고에 익숙해지면 훨씬 더 편하다는 이야기를 들었던 기억이 난다.
이제는 for문을 여러개 쓰는 것 보다 재귀함수를 쓰는게 더 편한 것 같다.
하나씩 깨닫고 배울때 마다 기쁘다.
728x90
