Lv0 - 약수 구하기 (약수 알고리즘)(자바)

문제설명

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

 

입출력 

n	result
24	[1, 2, 3, 4, 6, 8, 12, 24]
29	[1,29]

 

생각정리 

1. 약수 구하기

for (int i=1; i<=Math.sqrt(n); i++) // n 제곱수 까지만 검사
    if(n%i == 0) {    // 약수인지 확인
        list.add(i);
        if (n/i != i) {  // 약수로 확인된 값으로 n을 나눈 값 약수판정
            list.add(n/i);

 - for 문에서 n의 제곱수 까지만 반복한다 왜 그럴까? 입출력 예시 24를 보자

  1, 2, 3, 4, 6, 8, 12, 24    - > 빨간 숫자와 파란 숫자는 각각 곱하면 24가 된다.  이번에는 100의 약수를 구해보자

  1, 2, 4, 5, 10, 20, 25, 50, 100 -> 100의 제곱수 10을 기점으로 빨간 글씨와 파란글씨가 바뀐다. 

 

정수 n 의 제곱수 (int 정수) 만 포함한 수까지 약수임을 판별하고 파란글씨 숫자는 앞에서 구한 약수  i로 나눈 값

 

2. 배열은 크기를 바꾸기 쉽지 않으므로 ArrayList에 값을 담은뒤, 정렬하고 배열로 반환하는 코드를 짜면 완성

import java.util.*;

class Solution {
    public int[] solution(int n) {
        ArrayList <Integer> list = new ArrayList<Integer>();
        
        for (int i=1; i<=Math.sqrt(n); i++) {
            if(n%i == 0) {
                list.add(i);
                if (n/i != i) {
                    list.add(n/i);
                }
            }
        }
        // ArrayList 정렬
        Collections.sort(list); 
        
        // 배열을 ArrayList 크기만큼 생성하고 값을 담는다.
        int [] answer = new int [list.size()];
        for (int i=0; i<answer.length; i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}