2024. 8. 12. 18:00ㆍ코딩테스트 입문
https://school.programmers.co.kr/learn/courses/30/lessons/120852
문제 설명
소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.
제한사항
- 2 ≤ n ≤ 10,000
입출력 예
n | result |
12 | [2, 3] |
17 | [17] |
420 | [2, 3, 5, 7] |
입출력 예 설명
입출력 예 #1
- 12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.
입출력 예 #2
- 17은 소수입니다. 따라서 [17]을 return 해야 합니다.
입출력 예 #3
- 420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.
숫자를 소인수 분해하는 문제입니다.
소인수 분해는 항상 난감한 문제죠. 생각보다 소수를 구하는 게 쉽지 않습니다.
가장 처음에 생각해낸 방법은 tar라는 나누는 값을 설정하고, n을 tar로 나눴을 때 나머지가 생길 때까지 반복하는 구조로 코드를 짜면 되지 않을까 했습니다.
이 방법으로 작성한 코드는 아래와 같습니다.
def solution(n):
# 소인수를 집합으로 저장
answer = set()
# 시작값 2로 설정
tar = 2
# n이 1이 될 때까지 반복
while n > 1:
# 나머지가 남는다면 tar 증가
if n % tar:
tar += 1
# 나머지가 남지 않는다면
else:
# n을 tar로 나누고
n /= tar
# answer에 추가
answer.add(tar)
# 집합을 리스트로 전환 후 정렬
answer = sorted(list(answer))
return answer
곰곰히 생각해보니까 굳이 n > 1로 설정하지 말고, tar를 기준으로도 while문 반복을 끝낼 수도 있었습니다.
n의 약수를 셀 때 sqrt(n)까지만 반복하면 되는 것처럼, 이 문제에서도 tar ** 2로 종료 조건을 설정할 수 있습니다.
def solution(n):
# 초기값 설정
answer, tar = [], 2
# tar가 sqrt(n)까지만 반복
while tar ** 2 <= n:
# 나머지가 남는다면 tar 증가
if n % tar:
tar += 1
# 나머지가 남지 않는다면(배수라면)
else:
# tar 추가
answer.append(tar)
# 해당 배수가 남지 않을 때까지 반복
while n % tar == 0:
n //= tar
# 남아있는 소수가 있는 경우 (n > 1 이면 그 자체가 소수)
if n > 1:
answer.append(n)
return answer
좀 더 효율적으로 작성해본 코드는 다음과 같습니다.
tar의 반복 범위를 줄였고, 한 번 소인수인 것이 확인되면 해당 소인수가 사라질 때까지 반복하도록 했습니다.
마지막에는 n > 1 조건을 설정해줬는데요, 이 조건은 n 자체가 소수일 때를 위해서입니다.
17 같은 케이스도 tar가 17까지는 진행하지 못하기 때문에 이렇게 따로 추가를 해줘야 합니다.
소인수 문제는 언제나 생각할 게 많은 문제 같네요.
'코딩테스트 입문' 카테고리의 다른 글
배열 원소의 길이 (0) | 2024.08.14 |
---|---|
컨트롤 제트 (0) | 2024.08.13 |
숨어있는 숫자의 덧셈 (1) (0) | 2024.08.11 |
문자열 정렬하기 (1) (0) | 2024.08.10 |
모음 제거 (0) | 2024.08.09 |