날짜: 2022년 1월 31일 오후 5:51
코드
Algorithm/42839.py at main · Junroot/Algorithm
풀이
- 종이 조각으로 만들 수 있는 모든 수 구하기
- 만들어진 수 중에 가장 큰 수 이하의 모든 소수 구하기
- 소수 리스트에 만들어진 수가 포함된 것의 개수 구하기
이렇게 3가지 소문제로 나눴다. 이렇게 접근한 이유는 숫자마다 소수인지 검증하는 과정을 매번 계산하는 것이 비효율적이라고 생각했기 때문이다.
1번 문제의 경우 파이썬의 itertools라는 모듈에 permutations 함수를 사용해도되지만 이번에는 모든 순열을 구하는 함수를 직접 구해봤다. get_permutations 함수를 참고하면된다.
- digits에 숫자를 하나씩 꺼낸다.
- 해당 숫자를 제외하고 나머지 숫자들로 나올 수 있는 모든 순열을 구한다(재귀)
- 2번에서 구한 순열들의 앞에 1번에서 꺼낸 숫자를 붙이는 경우와 안붙이는 경우를 모두 구한다.
이렇게 구하면 "" 와 중복된 순열이 나오는데 filter와 set을 이용하여 해결했다.
2번 문제는 에라토스테네스의 체를 이용하면 된다. 이 때 주의할 점이 한 가지 있다. 해당 숫자가 소수인지 아닌지 확인할 때, (자신의 숫자) ** 0.5 까지만 나누어 떨어지는지 확인하면 된다는 것이다. 이것 만으로도 계산 시간이 확 줄어든다.
3번 문제는 2번에서 구한 소수 리스트가 이미 정렬된 형태기 때문에, 이분탐색을 사용했다.
1, 2번에서 실수하면 계산 시간이 길어져서 푸는데 어려움을 겪었다.
다른 사람 풀이를 보는데 너무 깔끔해서 이 풀이도 한 번 정리해보기로 했다.
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)
- 가능한 모든 수를 구한다.
- 2부터 (만들어진 수의 최대값) ** 0.5 까지를 루프를 돌면서 i의 자신을 제외한 모든 배수들을 제거한다.
가능한 수 조합에서 에라토스테네스의 채를 이용해버리면 된다고는 생각하지 못했는데 그 부분이 너무 좋았다.