[코딩테스트] 프로그래머스 120897 약수 구하기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120897

프로그래머스

 

접근방법

1. 정수 n이 주어질때 1 ~ n의 제곱근까지 순회하여 반복문 변수 i가 n으로 나누어 떨어지는지 확인

• 나누어 떨어진다면 i는 n의 약수

2. 리스트에 변수 i와 n / i의 결과를 추가

• i가 n의 약수라면 n / i 또한 약수이기 때문입니다.

3. 리스트를 오름차순으로 정렬 후 정수형 배열로 변환하여 결과를 반환

 

예시

예를 들어 n = 24인경우 n의 제곱근은 4.xxx이므로 반복문 변수 i는 1~4까지 진행됩니다. 이때 1 ~ 4중 24가 나누어 떨어지는 약수는 1, 2, 3, 4입니다. 또한 24를 1, 2, 3, 4로 나눈 몫인 24, 12, 8, 6또한 24의 약수임을 알 수 있습니다.

 

주의사항

n=1인경우 리스트에 [1,1]과 같이 되기 때문에 배열 변환 과정중 distinct()를 호출하여 중복을 제거합니다.

 

시간복잡도

• 단순히 i=1 ~ n까지 순회하여 약수를 구하는 경우 O(n)이 소요되지만 i를 제곱근 까지만 반복하면 O(제곱근(n))로 줄일 수 있습니다.

 

코드

class Solution {
    public int[] solution(int n) {
        int[] answer = {};
        List<Integer> divisors = new ArrayList<>();
        for(int i = 1; i*i <= n; i++){
            if(n % i == 0){
                divisors.add(i);
                divisors.add(n / i);
            }
        }

        Collections.sort(divisors);
        answer = divisors.stream().mapToInt(Integer::intValue).distinct().toArray();
        return answer;
    }
}