[프로그래머스] Lv.1 약수의 합 - 자바[Java]

🔥개인 취미 목적으로 프로그래머스 문제를 정리한 게시글입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12928?language=java

프로그래머스

✏️ 문제설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해 주세요.

💡 제한사항

n은 0 이상 3000 이하인 정수입니다.

📚 입출력 예

n	return
12	28
5	6

---

💻 소스 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                answer += i;
            }
        }
        
        return answer + n;
    }
}

주어진 코드는 정수 n을 입력으로 받아서 n의 약수를 모두 더한 값을 반환하는 함수입니다.

코드의 동작을 다음과 같이 설명할 수 있습니다.

1. 결과를 저장할 정수 변수 answer를 0으로 초기화합니다.
2. 1부터 n / 2까지의 모든 정수를 순회하는 for 루프를 사용합니다. 이 범위를 선택하는 이유는 n의 약수는 n 자체를 포함하여 n / 2를 넘어가지 않기 때문입니다. 이렇게 하면 반복 횟수를 절반으로 줄일 수 있습니다.
3. 루프 내에서, 현재 숫자 i가 n의 약수인지 확인하기 위해 n을 i로 나눈 나머지를 계산합니다.
4. 만약 n을 i로 나눈 나머지가 0이라면, i는 n의 약수입니다. 이 경우, i를 answer에 더합니다.
5. 모든 숫자를 순회한 후에는 answer에 n을 더하여 최종적인 결과를 계산합니다. 이렇게 함으로써 n 자체도 약수로 처리됩니다.
6. 최종적으로 answer에는 n의 모든 약수를 더한 값이 저장되고, 이 값을 반환합니다.

이 코드는 입력된 정수 n의 약수를 모두 구하고 더하는 간단한 방법을 사용하여 결과를 반환합니다.

시간 복잡도

위 코드의 시간 복잡도는 1부터 n의 절반까지 반복문을 실행하기 때문에 시간 복잡도는 O(n)입니다.

여기서 n은 입력된 정수 n의 값에 비례합니다.

공간 복잡도

사용된 메모리 공간은 상수이기 때문에 입력된 값 n에 상관없이 사용되는 변수는 answer 하나뿐이기 때문에 공간 복잡도도 O(1)입니다. 입력값 n의 크기와 관계없이 항상 일정한 메모리 공간을 사용합니다.