[프로그래머스] 약수의 합

2024. 10. 13. 13:15·여러가지/알고리즘 & 자료구조

문제 설명
정수 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
'여러가지/알고리즘 & 자료구조' 카테고리의 다른 글
  • [프로그래머스] 자연수 뒤집어 배열로 만들기
  • [프로그래머스] 문자열 내 p와 y의 개수
  • [프로그래머스] 자릿수 더하기
  • [프로그래머스] 짝수와 홀수
hyeseong-dev
hyeseong-dev
안녕하세요. 백엔드 개발자 이혜성입니다.
  • hyeseong-dev
    어제 오늘 그리고 내일
    hyeseong-dev
  • 전체
    오늘
    어제
    • 분류 전체보기 (283) N
      • 여러가지 (107)
        • 알고리즘 & 자료구조 (72)
        • 오류 (4)
        • 이것저것 (29)
        • 일기 (1)
      • 프레임워크 (39)
        • 자바 스프링 (39)
        • React Native (0)
      • 프로그래밍 언어 (38)
        • 파이썬 (30)
        • 자바 (3)
        • 스프링부트 (5)
      • 운영체제 (0)
      • DB (17)
        • SQL (0)
        • Redis (17)
      • 클라우드 컴퓨팅 (2)
        • 도커 (2)
        • AWS (0)
      • 스케쥴 (65)
        • 세미나 (0)
        • 수료 (0)
        • 스터디 (24)
        • 시험 (41)
      • 트러블슈팅 (1)
      • 자격증 (0)
        • 정보처리기사 (0)
      • 재태크 (5) N
        • 암호화폐 (5) N
        • 기타 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백준
    Redis
    RDS
    Spring WebFlux
    AWS
    파이썬
    docker
    DP
    완전탐색
    Spring Boot
    spring
    ecs
    EC2
    java
    Docker-compose
    mybatis
    Python
    reactor
    #개발자포트폴리오 #개발자이력서 #개발자취업 #개발자취준 #코딩테스트 #항해99 #취리코 #취업리부트코스
    WebFlux
    시험
    취업리부트
    OOP
    celery
    FastAPI
    항해99
    그리디
    프로그래머스
    자바
    SAA
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
hyeseong-dev
[프로그래머스] 약수의 합
상단으로

티스토리툴바