약수 구하기 [CT]

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

생각한 풀이
1. ArrayList를 만들어 구한 약수들을 담는다
2. ArrayList 값을 배열에 담아 배열 출력

---

import java.util.ArrayList;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> answer = new ArrayList<>();
        for(int i=1;i<=n;i++){
            while(n%i==0){
                answer.add(i);
            }
        }
        
        int num[]= new int[answer.size()];
        for(int i=0;i<answer.size();i++){
            num[i]=answer.get(i);
        }
        
        return num;
    }
}

⚠️메모리 초과 발생
1. 약수의 수가 몇개인지 몰라 ArrayList로 생성
2. 1부터 for문을 돌려 약수 카운트
3. 해당 ArrayList를 배열로 변경해 출력

---

import java.util.ArrayList;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> answer = new ArrayList<>();
        for(int i=1;i*i<=n;i++){
            while(n%i==0){
                answer.add(i);
                if(i!=n/i){
                	answer.add(n/i);
                }
            }
        }
        
        int num[]= new int[answer.size()];
        for(int i=0;i<answer.size();i++){
            num[i]=answer.get(i);
        }
        
        return num;
    }
}

⚠️메모리 초과 발생
1. 방법은 동일하지만 약수를 카운트할때 i*i로 1부터 제곱근 n( sqrt(n) )까지 반복
2. 약수는 짝을 이루는 특성을 이용해 i부터 sqrt(n)까지 반복 (i<=sqrt(n) == i*i<=n)
3. 해당 방식을 사용하면 반복 횟수를 줄일 수 있다
4. 중복을 피하기 위해 i!=n/i( 약수가 짝을 이루는 특성)

여전히 메모리 초과 오류

---

import java.util.HashSet;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
    public int[] solution(int n) {
        HashSet<Integer> answer = new HashSet<>();

        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                answer.add(i);
                answer.add(n / i);
            }
        }
        
        ArrayList<Integer> result = new ArrayList<>(answer);
        Collections.sort(result);
        
        int[] arr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        
        return arr;
    }
}

🐴 풀이
1. 로직은 거의 똑같은데 HashSet은 중복 값을 허용안하기 때문에 중복 확인 제거
2. 정렬을 위해 HastSet을 ArrayList로 변경하고 오름차순 정렬 후 배열에 담아 출력

정렬해야 하는걸 이때 봤다