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

안녕하세요.

오늘은 프로그래머스의 코딩테스트 lv.0단계 중에 약구 구하기를 공부해보겠습니다.

언어는 Java로 구현하였습니다.

 

문제 설명

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

 

제한 사항

• 1 ≤ n ≤ 10,000

입출력 예

• 24의 약수를 오름차순으로 담은 배열 [1, 2, 3, 4, 6, 8, 12, 24]를 return합니다.
• 29의 약수를 오름차순으로 담은 배열 [1, 29]를 return합니다.

---

문제 풀이

약수를 구하기 위해 반복문을 사용해 매개변수를 1부터 n까지 나누며, 나머지가 0인 수를 배열에 담아 반환하였습니다.
약수의 개수를 미리 알 수 없기 때문에 우선 매개변수와 같은 크기의 임시 배열을 만들고 약수를 찾을 때마다 count를 증가시켰습니다.
이후 count 크기의 최종 배열을 생성하고 임시 배열에 담긴 약수들을 복사하여 최종 배열로 반환하도록 구현했습니다.

class Solution {
    public int[] solution(int n) {
        int[] temp = new int[n];  
        int count = 0;
 
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                temp[count] = i;
                
                count++;
            }
        }
 
        int[] answer = new int[count];
        
        for (int i = 0; i < count; i++) {
            answer[i] = temp[i];
        }
 
        return answer;
    }
}

 

추가 풀이

다른 분들의 풀이 중에 1부터 √n까지만 반복하며 약수를 구하는 방법이 있어서 공부해보았습니다.

import java.util.*;
 
class Solution {
    public int[] solution(int n) {
        List<Integer> list = new ArrayList<>();
 
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {  
                list.add(i);  
                
                if (i != n / i) {
                    list.add(n / i);
                }
            }
        }
 
        return list.stream().sorted().mapToInt(Integer::intValue).toArray();  
    }
}

 

이 방식은 1부터 n까지 전부 나누지 않고 1부터 √n까지만 반복하여 약수를 찾습니다.

약수는 항상 짝을 이루기 때문에 i가 약수라면 n / i 도 함께 약수가 됩니다.
예를 들어, 24의 약수는 [1-24], [2-12], [3-8], [4-6]처럼 쌍으로 구성됩니다.

따라서 반복문을 √n까지만 돌리면서 i가 약수일 경우 n / i 도 함께 추가하여 결과값을 얻게 되면 시간 효율성을 높일 수 있습니다.

이렇게 구한 약수들은 정렬되어 있지 않고 중복될 수 있으므로 stream() 함수를 사용해 정렬한 뒤 배열로 변환하여 최종 결과를 반환합니다.

---

사용 함수

• stream().sorted()
  • 배열을 정렬하는 함수로, 요소를 오름차순으로 정렬할 수 있습니다.
• mapToInt(Integer::intValue)
  • Integer 타입의 값을 int로 변환하여 배열로 반환하는 함수입니다.

 

마무리 정리

이번 문제는 약수를 구하는 방식에서 1부터 √n까지 반복하는 방법을 적용하여 시간 효율성을 높일 수 있다는 점을 배웠습니다.
앞으로 문제를 풀 때 시간 효율성도 고려하여 접근하도록 노력하겠습니다.

이상으로 프로그래머스 lv.0 - 약수 구하기 문제를 마치겠습니다.
감사합니다.