문제 설명
정수 n
이 주어졌을 때, n
의 모든 약수를 더한 값을 반환하는 함수를 작성하는 문제입니다. 예를 들어, n = 12
라면 약수는 1, 2, 3, 4, 6, 12이고, 이들의 합은 28입니다.
제한 사항
n
은 0 이상 3000 이하인 정수입니다.
입출력 예
n | return |
---|---|
12 | 28 |
5 | 6 |
- 입출력 예 #1: 12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.
- 입출력 예 #2: 5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.
문제 풀이
이 문제는 주어진 n
의 약수를 구하고, 그 합을 반환하는 문제입니다. 앞서 설명한 것처럼, 약수는 대칭적으로 존재하기 때문에 모든 약수를 구하기 위해서는 1부터 √n까지만 확인하면 됩니다. 다만, n
이 0일 경우 약수가 없기 때문에, 0에 대해서는 특별 처리가 필요합니다.
1. Python 코드 풀이
def solution(n):
if n == 0:
return 0
total = 0
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
total += i
if i != n // i: # 중복된 약수가 아니면 더함
total += n // i
return total
# 테스트 예시
print(solution(12)) # 출력: 28
print(solution(5)) # 출력: 6
코드 설명
n == 0
인 경우에는 약수가 없으므로 0을 반환합니다.- 그 외의 경우에는 1부터 √n까지 반복하면서
n
의 약수를 찾습니다. n % i == 0
이면,i
와n // i
는 모두n
의 약수이므로 합에 더합니다. 단,i
가n // i
와 같으면 중복된 값이므로 한 번만 더합니다.
2. Java 코드 풀이
class Solution {
public int solution(int n) {
int answer = 0; // 약수의 합을 저장할 변수
// 1부터 i*i <= n까지 반복
for(int i = 1; i*i <= n; i++){
if(n % i == 0){ // i가 n의 약수인지 확인
answer += i; // i가 약수이면 i를 더함
// i와 n / i가 다른 경우에만 추가로 n / i를 더함 (중복 방지)
if(i != n / i ){
answer += n / i;
}
}
}
return answer; // 모든 약수를 더한 결과를 반환
}
}
코드 설명
이 코드의 목적은 주어진 정수 n
의 약수의 합을 구하는 것입니다. 약수는 어떤 수를 나누었을 때 나머지가 0인 수를 말합니다. 이 코드는 약수의 성질을 이용하여 시간 복잡도를 효율적으로 줄이는 방식으로 작성되었습니다. 자세히 살펴보겠습니다.
코드 구조 및 설명
1. 변수 초기화
int answer = 0;
- 약수의 합을 저장할 변수
answer
를 0으로 초기화합니다. 이 변수는 최종적으로 약수들을 모두 더한 값을 반환합니다.
2. 반복문: 약수 탐색
for(int i = 1; i * i <= n; i++){
- 반복문은
i = 1
부터 시작하여i * i <= n
조건이 만족될 때까지 실행됩니다. 즉,i
가n
의 제곱근 이하일 때만 반복됩니다.- 약수는 대칭적으로 존재합니다. 예를 들어,
n = 36
일 경우(1, 36)
,(2, 18)
,(3, 12)
,(4, 9)
,(6, 6)
처럼 나타나므로n
의 제곱근까지만 확인하면 나머지 큰 약수는 자동으로 구할 수 있습니다. - 이 때문에
i
가√n
이하일 때까지만 반복문을 실행하여 시간을 절약할 수 있습니다.
- 약수는 대칭적으로 존재합니다. 예를 들어,
3. 약수 확인
if(n % i == 0){
n % i == 0
조건은n
을i
로 나누었을 때 나머지가 0인지, 즉i
가n
의 약수인지를 확인하는 조건입니다.- 만약
n % i == 0
이면i
는n
의 약수입니다.
- 만약
4. 약수 더하기
answer += i;
i
가 약수로 확인되면, 이를answer
에 더합니다.
5. 대칭 약수 더하기 (중복 방지)
if(i != n / i ){
answer += n / i;
}
- 이 조건은
i
와n / i
가 서로 다른 경우에만n / i
도answer
에 더하는 부분입니다.- 예를 들어,
n = 36
일 때,i = 2
이면n / i = 18
이므로2
와18
을 동시에 더해야 합니다. - 하지만
i = 6
일 때는n / i
도 6이므로 이 값은 한 번만 더해야 합니다. 즉,i
와n / i
가 같은 경우에는 중복을 방지하기 위해 한 번만 더해줍니다.
- 예를 들어,
6. 결과 반환
return answer;
- 모든 약수를 더한 후
answer
를 반환합니다.
작동 원리 예시
예를 들어,
n = 36
일 때:- i = 1 → 1은 36의 약수, answer += 1 → 대칭 약수 36도 더함 → answer += 36 (answer = 37)
- i = 2 → 2는 36의 약수, answer += 2 → 대칭 약수 18도 더함 → answer += 18 (answer = 57)
- i = 3 → 3은 36의 약수, answer += 3 → 대칭 약수 12도 더함 → answer += 12 (answer = 72)
- i = 4 → 4는 36의 약수, answer += 4 → 대칭 약수 9도 더함 → answer += 9 (answer = 85)
- i = 6 → 6은 36의 약수, answer += 6 → 6과 6이 동일하므로 한 번만 더함 (answer = 91)
- 이후
i
가√36 = 6
을 넘으므로 반복문 종료.
결과: 36의 모든 약수(1, 2, 3, 4, 6, 9, 12, 18, 36)를 더한 값인 91을 반환합니다.
시간 복잡도 분석
- 반복문은 1부터
√n
까지 실행되므로 시간 복잡도는 O(√n)입니다. - 이 코드는
n
이 최대 3000까지 가능하므로 매우 효율적입니다.
결론
이 문제는 약수를 구하는 전형적인 문제로, 약수의 대칭성을 이용하면 시간 복잡도를 O(√n)으로 최적화할 수 있습니다. 이를 통해 제한 조건 내에서 매우 효율적으로 문제를 해결할 수 있습니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[프로그래머스] 자연수 뒤집어 배열로 만들기 (0) | 2024.10.14 |
---|---|
[프로그래머스] 문자열 내 p와 y의 개수 (1) | 2024.10.14 |
[프로그래머스] 자릿수 더하기 (1) | 2024.10.13 |
[프로그래머스] 짝수와 홀수 (0) | 2024.10.13 |
[프로그래머스] x만큼 간격이 있는 n개의 숫자 (0) | 2024.10.13 |