약수 구하기
2024. 9. 12. 18:00ㆍ코딩테스트 입문
https://school.programmers.co.kr/learn/courses/30/lessons/120897
문제 설명
정수 n이 매개변수로 주어질 때, n의 약수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ n ≤ 10,000
입출력 예
n | result |
24 | [1, 2, 3, 4, 6, 8, 12, 24] |
29 | [1, 29] |
입출력 예 설명
입출력 예 #1
- 24의 약수를 오름차순으로 담은 배열 [1, 2, 3, 4, 6, 8, 12, 24]를 return합니다.
입출력 예 #2
- 29의 약수를 오름차순으로 담은 배열 [1, 29]를 return합니다.
주어진 숫자 n의 모든 약수를 오름차순 정렬하는 문제입니다.
사실 단순히 반복문을 사용해서 전부 찾으면 되기는 한데, 결국 약수들은 모두 한 쌍 구조이기 때문에 약수로 나눈 몫이 또 약수기도 합니다. 그래서 제곱근 전까지만 해도 된다는 게 이런 특성때문입니다.
어쨌든 전부 탐색하는 것 한 번, 그리고 좀 더 개량할 수 있는지도 한 번 확인해보겠습니다.
def solution(n):
# n을 num으로 나눴을 때 나머지가 0이면 약수 관계이다.
answer = [num for num in range(1, n+1) if n % num == 0]
return answer
반복문을 사용해서 모든 범위를 탐색하는 방법입니다.
조건문으로 나눈 나머지가 0이면 배수 관계라는 걸 이용해서 문제를 풀었습니다.
집합을 사용해서 중복값 (36일 때 6 같은 경우) 을 처리하는 방법입니다.
이 경우에 범위를 제한해서 문제를 풀어보았습니다.
from math import sqrt
def solution(n):
answer = set()
for num in range(1, int(sqrt(n)) + 1):
if n % num == 0:
answer.add(num)
answer.add(n // num) # n을 num으로 나눈 결과도 추가
# 리스트 변환 및 오름차순 정렬
answer = sorted(list(answer))
return answer
반복문에서 효율적으로 구성된 것 같네요.