📜문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
📍제한 사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
📍입출력 예시
| nums | result |
|---|---|
| "17" | 3 |
| "011" | 2 |
📄문제 해결
📝내가 푼 코드
✅ 1차 시도
import itertools
# 소수 판별 함수
def check(num):
if num in [0, 1]: return False
for n in range(2, num):
if num%n==0:
return False
return True
def solution(string):
numbers = list(map(int, string))
answer = set()
for i in range(1, len(numbers)+1):
# 순열 함수로 숫자 조합 탐색
for perm in itertools.permutations(numbers, i):
num = int(''.join(map(str,perm)))
if check(num):
answer.add(num)
return len(answer)이번 문제는 순열을 빠르게 떠올리면서 permutations() 함수를 활용해 쉽게 풀 수 있었다.
문제에서는 numbers로 숫자를 만들 수 있는 각각의 정수를 제공하는데, 이때 만들 숫자의 길이는 한 자리부터 최대 numbers의 길이까지이므로 가능한 길이에 따라 permutations() 함수를 활용해 순열 조합을 만들어 소수인지 판별한 뒤 맞을 경우 집합에 추가했다.
처음에는 answer 변수를 집합이 아닌, 단순히 int형으로 조건에 부합할 때마다 1씩 더하는 방식으로 구현하였는데 numbers에서 제공된 정수 중에서 중복이 있을 경우 조합을 만드는 과정에서 중복된 조합을 만들어내기 때문에 잘못된 결과를 야기하였다. 하지만 조합을 활용해 결괏값을 저장하고, len() 함수로 길이를 반환하니 올바른 결과를 도출할 수 있었다.
중복된 순열이 발생함에 있어 집합으로 중복 집계되는 문제는 해결하며 문제는 성공적으로 풀 수 있었다. 하지만, 코드를 다시 돌아보며 중복된 순열에 대해서 또다시 소수인지 검사하는 함수를 호출하는 것이 불필요하게 느껴져 코드를 조금 수정해보기로 했다.
✅ 2차 시도 (+약간의 최적화)
import itertools
# 소수 판별 함수
def check(num):
if num in [0, 1]: return False
for n in range(2, num):
if num%n==0:
return False
return True
def solution(string):
numbers = list(map(int, string))
case = list()
answer = 0
for i in range(1, len(numbers)+1):
# 순열 함수로 숫자 조합 탐색
for perm in itertools.permutations(numbers, i):
num = int(''.join(map(str,perm)))
if num not in case and check(num):
case.append(num)
answer += 1
return answer전반적인 로직은 같지만, 소수로 판별하기 전에 이전에 검사한 순열인지 확인하는 과정을 추가했다. 중복된 값이 아니지만 소수로 판별되는 경우 집합이 아닌 리스트에 순열을 저장하도록 하였고, answer 변수를 활용해 소수의 개수를 카운트하도록 하였다.
아래는 1차 시도에서 도출된 결과이고, 화살표 뒤에 있는 것은 2차 시도에서 도출된 결과이다. 모든 테스트의 실행 시간이 개선된 것은 아니지만, 테스트2, 4, 5, 10, 12의 경우 눈에 띄게 실행 시간이 절약된 것을 확인할 수 있다!
테스트 1 〉 통과 (0.33ms, 10.2MB) => (0.40ms, 10.4MB)
테스트 2 〉 통과 (186.01ms, 10.4MB) => (0.40ms, 10.4MB)
테스트 3 〉 통과 (0.03ms, 10.5MB) => (0.04ms, 10.3MB)
테스트 4 〉 통과 (151.68ms, 10.3MB) => (10.41ms, 10.3MB)
테스트 5 〉 통과 (30.53ms, 10.4MB) => (23.67ms, 10.3MB)
테스트 6 〉 통과 (0.04ms, 10.2MB) => (0.04ms, 10.4MB)
테스트 7 〉 통과 (0.52ms, 10.3MB) => (0.18ms, 10.4MB)
테스트 8 〉 통과 (23.47ms, 10.4MB) => (29.12ms, 10.3MB)
테스트 9 〉 통과 (0.07ms, 10.3MB) => (0.04ms, 10.4MB)
테스트 10 〉통과 (3050.66ms, 10.3MB) => (2251.65ms, 10.4MB)
테스트 11 〉통과 (87.45ms, 10.2MB) => (79.68ms, 10.4MB)
테스트 12 〉통과 (2.67ms, 10.3MB) => (0.92ms, 10.3MB)🤔느낀점
이전에 순열 함수를 활용해 문제를 한 번 풀고나니 이후에 순열과 조합을 사용하는 문제는 수월하게 풀리는 것 같다. 제출 후에도 블로그를 작성하며 코드를 보니 추가적으로 최적화할 만한 부분이 더올라 수정하고 유효한 효과를 확인하여 뿌듯했지만, 기왕은 문제를 풀 때 좀 더 깊게 생각해보면 좋겠다는 생각이 들었다.
나는 소수를 판별할 때 단순히 각 순열로부터 도출된 정수를 반복문으로 검사했으나, 에라토스테네스의 체라는 방법론을 활용하지 못해 아쉬움이 남았다. 몇 년 전 공부했던 내용이었던 것 같은데 새까맣게 까먹어버린 바람에.. 다음에 복습하며 이 문제에 적용해 다시 한 번 풀어보고 싶다.
