[백준/JAVA]9506번 약수들의 합

문제

https://www.acmicpc.net/problem/9506

어떤 수 n이 완전수인지 판단하는 문제였다. 완전수란 자기 자신을 제외한 약수의 합이 자기 자신과 같은 수이다.

문제 풀이

처음에는 N의 약수를 N 크기의 배열에 저장했지만 N이 커질수록 불필요한 메모리 낭비가 발생했다. 실제로 약수의 개수는 N보다 훨씬 적기 때문에 배열은 비효율적이다. 이를 개선하기 위해 동적으로 크기를 조절할 수 있는 ArrayList를 사용해 문제를 해결했다.

1. 배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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;
			
			int sum=0;
			int[] array=new int[N];
			int count=0; //배열에 저장될 약수 개수
			for(int i=1;i<N;i++) {
				if(N%i==0) {
					sum+=i;
					array[count++]=i; //배열에 약수 저장
				}
			}
			
			if(sum==N) {
				StringBuilder sb=new StringBuilder();
				sb.append(N).append(" = ");
				for(int i=0;i<count;i++) {
					sb.append(array[i]);
					if(i!=(count-1)) {
						sb.append(" + ");
					}
				}
				System.out.println(sb);
			}
			else {
				System.out.println(N+" is NOT perfect.");
			}
		}
	}		
}

2.  ArrayList

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

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;
			
			int sum=0;
			List<Integer> list=new ArrayList<>();
            
			for(int i=1;i<N;i++) {
				if(N%i==0) {
					sum+=i;
					list.add(i); //ArrayList에 약수 추가
				}
			}
            
			if(sum==N) {
				StringBuilder sb=new StringBuilder();
				sb.append(N).append(" = ");
				for(int i=0;i<list.size();i++) {
					sb.append(list.get(i));
					if(i!=(list.size()-1)) {
						sb.append(" + ");
					}
				}
				System.out.println(sb);
			}
			else {
				System.out.println(N+" is NOT perfect.");
			}
		}
	}		
}