[9506] 약수들의 합

[Bronze I] 약수들의 합 - 9506

문제 링크

성능 요약

메모리: 16512 KB, 시간: 176 ms

분류

구현(implementation), 수학(math), 정수론(number_theory)

문제 설명

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

입력

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)

입력의 마지막엔 -1이 주어진다.

출력

테스트케이스 마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다(예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

아이디어

• 구현 방법 각 숫자들의 약수들을 담은 리스트를 만들어
  stream api를 활용하여 총 합을 구한 뒤
  완전수 여부에 따라 결과를 출력한다.

• 약수를 구하는 방법

  • 1부터 n까지 for문으로 하나씩 증가시키면서 나누어 떨어지는지 검사한다.
  • loop의 수를 줄이기 위해 제곱근을 구하는 Math.sqrt()를 사용하였다.

답안코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while(true) {
            int n = Integer.parseInt(br.readLine());
            if (n == -1) break;
            
            List<Integer> nums = new ArrayList<>(); // 약수들을 담을 리스트

            int sqrt = (int)Math.sqrt(n);   // 제곱수
            for (int i = 1; i <= sqrt; i++) {
                if (n % i == 0) {
                    nums.add(i);    // 약수 중 작은 수
                    if (n / i != i) {  // 제곱근 두 번 추가 방지
                        nums.add(n / i);    // 약수 중 큰 수
                    }
                }
            }
            Collections.sort(nums); // 약수 모음 오름차순 정렬
            nums.remove(nums.size() - 1);   // 맨 마지막 수(자기 자신) 제거

            int sum = nums.stream().mapToInt(i -> i.intValue()).sum();  // 자기 자신을 제외한 약수들의 총 합
            
            String result;
            if (sum == n) {
                String sumString = nums.stream()    // Stream<Integer>
                    .map(i -> i.toString()) // Stream<String>
                    .collect(Collectors.joining(" + "));    // "1 + 2 + 3"
                result = n + " = " + sumString + "\n";
                bw.write(result);
            } else {
                result = n + " is NOT perfect.\n";
                bw.write(result);
            }
        }
        bw.flush();
        bw.close();
    }
}

BOJ 카테고리 내 다른 글 보러가기