약수 구하기

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

 

반복문에서 효율적으로 구성된 것 같네요.