[9506] 약수들의 합

난이도: ★★☆☆☆ • solved on: 2025-07-15

---

문제 요약

• 문제 유형: 구현 (완전수 판별)
• 요구사항: 입력으로 주어지는 양의 정수 n에 대해, n이 완전수(perfect number)이면 “n = 약수1 + 약수2 + …” 형태로 출력하고, 그렇지 않으면 “n is NOT perfect.”를 출력해야 한다. 입력이 –1이면 종료한다.

---

사용 개념

1. 자료구조

   • StringBuilder : 문자열 누적 및 재사용
   • List<Integer> : 약수 저장 및 정렬 (방법 2)

2. 알고리즘/기법

   • 반복문
   • 제곱근 활용 최적화

3. 핵심 키워드

   • 완전수(perfect number)
   • 약수(divisor)

---

풀이 아이디어 및 코드

방법 1: 단순 반복문 + StringBuilder 재사용

1. 문제 분해

   • n이 –1이 입력될 때까지 반복
   • 1부터 n–1까지 모든 약수를 탐색하여, 나누어떨어지면 sum에 더하고 StringBuilder에 “ + i” 형태로 누적
   • 반복 종료 후 sum == n인지 확인해 완전수 여부 출력

2. 핵심 로직 흐름

   while (true) {
     n 입력
     if (n == -1) break
     sum = 1
     sb.setLength(0)
     sb.append(" = 1")
     for (i = 2; i < n; i++) {
       if (n % i == 0) {
         sb.append(" + ").append(i)
         sum += i
       }
     }
     if (sum == n)
       출력(n + sb.toString())
     else
       출력(n + " is NOT perfect.")
   }

3. 예외 처리

   • n = 1인 경우: 1은 완전수가 아니므로 “1 is NOT perfect.” 출력

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == -1) break;
            int sum = 1;
            sb.setLength(0);
            sb.append(" = 1");
            for (int i = 2; i < n; i++) {
                if (n % i == 0) {
                    sb.append(" + ").append(i);
                    sum += i;
                }
            }
            if (sum == n) {
                System.out.println(n + sb.toString());
            } else {
                System.out.println(n + " is NOT perfect.");
            }
        }
    }
}

---

방법 2: 제곱근 활용 최적화 + String.join method 사용

1. 문제 분해

   • 약수는 짝을 이루므로 2부터 √n까지만 탐색
   • i가 약수면 i와 n/i를 동시에 추가
   • String.join method로 최종 문자열 조립

2. 핵심 로직 흐름

   for (i = 2; i <= √n; i++) {
     if (n % i == 0) {
       add i, add (n/i) (중복 방지)
       sum += i + (i != n/i ? n/i : 0)
     }
   }
   정렬 후 " + " 구분자로 문자열 생성
   sum == n 확인 후 출력

3. 예외 처리

   • √n이 정수일 때 i == n/i 조건으로 중복 추가 방지

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == -1) break;
            List<Integer> divisors = new ArrayList<>();
            divisors.add(1);
            int sum = 1;
            int root = (int) Math.sqrt(n);
            for (int i = 2; i <= root; i++) {
                if (n % i == 0) {
                    divisors.add(i);
                    if (i != n / i) divisors.add(n / i);
                    sum += i + (i != n / i ? n / i : 0);
                }
            }
            if (sum == n) {
                Collections.sort(divisors);
                String result = String.join(" + ",
                  divisors.stream().map(String::valueOf).toArray(String[]::new));
                System.out.println(n + " = " + result);
            } else {
                System.out.println(n + " is NOT perfect.");
            }
        }
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(n)
• 공간 복잡도: O(n) (문자열 버퍼 및 출력용)

방법 2

• 시간 복잡도: O(√n · log√n) (정렬 포함)
• 공간 복잡도: O(√n)

---

어려웠던 점

• for문을 최소화할 방법이 명확하지 않았다. -> 제곱근을 활용한 최적화 방법이 있었다.
• 완전수가 아닐 때 합이 n보다 작은 경우를 처음엔 고려하지 못해 오답을 제출했었다.
• StringBuilder 초기화 방법을 몰라 블로그를 참고했고, String Joiner 또한 배울 수 있었다.

---

배운 점 및 팁

• 제곱근 최적화로 반복 횟수를 크게 줄일 수 있다.
• StringJoiner나 새 인스턴스 생성은 가독성을 높이고 초기 용량 비용이 크지 않을 때 유용하다.
• 반대로 StringBuilder 재사용(setLength(0))은 Garbage Collection 부담을 줄이고, 반복 생성/삭제 비용을 절감해 성능에 민감한 상황에서 더 효율적이다.

  • Garbage Collection 부담을 줄인다는건 JVM이 힙(Heap) 메모리에서 “쓸모없어진 객체”를 찾아서 삭제하고 메모리를 회수하는 작업을 덜 하게 만든다는 의미이다.

• 일상적 코딩에서는 명확성과 유지보수성을 위해 새 인스턴스를 생성해도 무방하다.
• StringJoiner(CharSequence delimiter, CharSequence prefix, CharSequence suffix)는 구분자를 포함해 String을 출력해야할 때 유용하다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/9506
• 참고 블로그/깃허브: https://futurecreator.github.io/2018/06/02/java-string-joiner/

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • [7588] Amicable Numbers (짝수 약수 합 계산 후 다른 수와 쌍을 이루는 완전수 확장)
  • [6975] Abundant and Deficient Numbers (약수 합이 큰지 작은지 분류)

• 확장 문제 (GPT 추천):

  • 주어진 범위 내 모든 완전수 출력
  • 약수 합이 주어진 값 $k$인 수 찾기
  • 최댓값 $n$보다 작은 최대 완전수 찾기