[프로그래머스 LV.0] 약수 구하기

목차

문제 설명

정수 n이 매개변수로 주어질 때, n의 약수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ n ≤ 10,000

 

 

정수란?

**정수(Integer)**는 수학에서 자연수, 음의 자연수, 그리고 0을 포함하는 수를 말한다. 정수는 소수나 분수가 아닌 순수한 "완전한 수"로 이해할 수 있다. 예를 들어, -3, 0, 4는 모두 정수이다. 정수의 집합은 다음과 같이 표현한다.

 

여기서 Z는 독일어 "Zahlen"(숫자들)에서 유래한 기호다.

---

약수란?

**약수(Divisor)**는 어떤 정수를 나누었을 때 나머지 없이 나눌 수 있는 다른 정수를 말한다. 예를 들어, 6의 약수는 1, 2, 3, 6이다. 이는 다음과 같은 조건을 만족하는 정수 aaa와 bbb 사이의 관계로 정의된다.

 

여기서 c는 또 다른 정수이다.

---

약수의 특징

1. 자기 자신과 1은 모든 정수의 약수
   예를 들어, 12의 약수는 1과 12를 반드시 포함한다.
2. 약수의 개수는 짝을 이룬다
   정수 nnn이 있을 때, 약수는 곱셈의 형태로 쌍을 이룬다.
   예: 12의 약수 쌍은 (1, 12), (2, 6), (3, 4)이다.
3. 소수의 경우 약수는 1과 자기 자신뿐
   예: 7의 약수는 1과 7뿐이다.

---

약수를 찾는 방법

1. 정수를 작은 수부터 차례대로 나누어 본다.
2. 나눗셈의 나머지가 0이 되면 해당 수는 약수이다.

예제

18의 약수를 구해보자:

18의 약수는 1, 2, 3, 6, 9, 18이다.

---

약수와 배수의 관계

약수는 배수와 밀접한 관계를 가진다.

• 약수: 특정 수를 나눌 수 있는 작은 수
• 배수: 특정 수를 곱하여 얻는 큰 수

예제:

6의 배수는 6, 12, 18, 24, ...
6의 약수는 1, 2, 3, 6

---

활용 예시

1. 최대공약수(GCD)
   두 수의 공통된 약수 중 가장 큰 수.
   예: 12와 18의 최대공약수는 6.
2. 소인수분해
   수를 소수의 곱으로 표현.
   예: 18 = 2 X (3 X 3)
3. 프로그래밍에서 약수 계산
   약수를 계산하는 알고리즘은 수학적 최적화 문제를 해결하는 데 사용된다.

 

import java.util.*;
class Solution {
 	public int[] solution(int n) {
        List<Integer> arr = new ArrayList<>();
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                arr.add(i); // 작은 약수 추가
                if (i != n / i) { // 대칭되는 큰 약수 추가
                    arr.add(n / i);
                }
            }
        }
        // 오름차순 정렬 후 배열로 변환
        return arr.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

Math.sqrt(n) 대신 n까지 반복하는 방식은 동작은 동일하지만, 시간 복잡도의 측면에서 큰 입력값이 주어졌을 때 성능에 큰 차이를 만들어낸다.

 

쉽게 말해 n을 사용하면 n까지 모든 숫자를 돌아가며 검사하는 식보다 sqrt한 n을 사용하면 연산의 횟수가 확실히 줄어들기 때문이다.

 

public class Main {
    public static void main(String[] args) {
        int n = 1000000; // 테스트 숫자

        // Math.sqrt(n) 방식
        long start1 = System.nanoTime();
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                // 약수 처리
            }
        }
        long end1 = System.nanoTime();
        System.out.println("Math.sqrt(n) 방식 실행 시간: " + (end1 - start1) + "ns");

        // n까지 반복 방식
        long start2 = System.nanoTime();
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                // 약수 처리
            }
        }
        long end2 = System.nanoTime();
        System.out.println("n 반복 방식 실행 시간: " + (end2 - start2) + "ns");
    }
}

위의 예시 코드를 실행해보자.

 

Math.sqrt(n) 방식 실행 시간: 36125ns
n 반복 방식 실행 시간: 4538167ns 와 같은 결과가 나오느데 엄청난 시간 단축이다.