문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
📌 내 풀이
from itertools import permutations
def isPrime(num):
for i in range(2,int(num/2)+1):
if num % i == 0:
return False
return True
def solution(numbers):
answer = 0
visited = []
for i in range(1,len(numbers)+1):
for p in permutations(numbers, i):
num = int(''.join(p))
if num == 0 or num == 1: continue
if num in visited: continue
visited.append(num)
if isPrime(num):
answer += 1
return answer요약하자면 순열을 구하는 모듈을 사용해서, 하나의 경우의 수마다 소수인지 아닌지 판별하게끔 했다.
이왕 permutations()가 Generator 패턴을 반환하는거... 공간복잡도도 신경쓰면서 코딩했다. (그래서 list 변환을 해두지 않았다.)
소수 찾는 문제에는 에라토스테네스의 체로 구현하는게 국룰이긴 한데, 어떤 범위 내에서 모든 소수를 구하는게 아니라 특정 소수가 소순지 아닌지만 비교하면 되는 문제라.. 그렇게까지 할 필요가 없다고 생각했다.
한 가지 유의할 점은, 순열은 중복값을 구분하지 않는다.
예를 들어 (0,1,1) 이 TC로 주어진다 해보자. 여기서 2개의 원소로 순열을 만든다면 (1,1) 이 두번 나올 것이다. 같은 value라 하더라도 엄연히 다른 위치에 있는 원소기 때문이다.
그러나 이것까지 카운트한다면 같은 결과값을 중복해서 반영하게 된다. 코딩 설계할 때 생각하지 못한 부분이었다
그래서 위 코드에서 visited 리스트를 추가했던 것이다.
한번의 반복마다 O(n)만큼 추가되기에 썩 이쁜 방법이라고 생각하지 않는다...
시간제한이 조금 괴팍한 문제였다면 얄짤 없었을 것이다.
📌 다른 사람의 풀이
from itertools import permutations
def solution(n):
a = set()
for i in range(len(n)):
a |= set(map(int, map("".join, permutations(list(n), i + 1))))
a -= set(range(0, 2))
for i in range(2, int(max(a) ** 0.5) + 1):
a -= set(range(i * 2, max(a) + 1, i))
return len(a)와...
와........
집합의 특성을 너무 예술적으로 반영한 풀이라 감탄했다.
이런 코드는 손으로 다시 써봐야한다. 내꺼로 만들자!!
✔ 배운 점
- 집합은 생각보다 다양하게 쓰일 수 있다.
- 중복 요소를 제거할 땐 집합으로 푸는걸 고려하자.
