[JAVA 기본 알고리즘] 백준 알고리즘 9506번 / 약수들의 합

이번문제는 두가지 방법으로 풀어보았습니다!

일단 문제를 처음 봤을때 떠올랐던 큐를 활용해서 푸는 방법으로 풀어보았습니다.

큐클래스에 대한 사전지식없이 이번 문제를 풀면서 라이브러리 설명을 읽으면서 해보았기 때문에

불필요한 메소드의 사용이 많았을 수도 있음을 양해 부탁드립니다!

 

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Queue<String> num = new LinkedList<>();
        Queue<String> q = new LinkedList<>(); 
        String a = null;
        Scanner sc = new Scanner(System.in);
        while(true) {
            a=sc.next();
            if(Integer.parseInt(a)==-1)break;
            num.offer(a);
        }
        while(true) {
            if(num.peek()==null)break;
            int per=0;
            for(int j=1;j<Integer.parseInt(num.element());j++) {
                if(Integer.parseInt(num.element())%j==0) {
                    q.offer(String.valueOf(j));
                    per=per+j;
                }
            }
            if(per==Integer.parseInt(num.element())) {
                System.out.print(num.element()+" = ");
                while(q.size()!=1) {
                    System.out.print(q.poll()+" + ");
                }System.out.println(q.poll());
            }else System.out.println(num.element()+" is NOT perfect.");
            q.clear();
            num.poll();
        }
    }
}
 
 

이런 방법으로 했을때에는 메모리가 9892KB 시간은 184MS가 걸렸습니다.

9892 KB

184 MS

다만 두번째에 소개해 드릴 배열로 푸는 방법에서는 

8628 KB

104 MS

메모리가 8626KB 시간은 104MS로 두 부분 모두에서 효율적이라는 결론이 나오기는 했지만, 배열로 문제를 해결하기 위해서는 

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int num[]=new int[100];
        int x[];
        int q=0;
        Scanner sc = new Scanner(System.in);
        while(true) {
            num[q]=sc.nextInt();
            if(num[q]==-1)break;
            q++;
        }q=0;
        while(true) {
            if(num[q]==-1)break;
            x= new int[100];
            int per=0;
            int o=0;
            for(int j=1;j<num[q];j++) {
                if(num[q]%j==0) {
                    x[o]=j;
                    o++;
                    per=per+j;
                }
            }
            int p=o;
            if(per==num[q]) {
                System.out.print(num[q]+" = ");
                for(o=0;o<p-1;o++) {
                    System.out.print(x[o]+" + ");
                }System.out.println(x[o]);
            }else System.out.println(num[q]+" is NOT perfect.");    
            o=0;
            q++;
        }
    }
}
 

위에서 보시는 바와 같이 수를 몇가지나 입력받을 지 모르는 상황에서 배열의 크기를 미리 지정해야 한다는 점이 

맞았다고 나오기는 했지만 정말 100%맞았는가에 대한 고민을 하게 만들었습니다. 저의 개인적인 생각으로는

입력이 얼마나 있을지 모르는 상황에서는 큐를 활용한 풀이가 더 맞는 방법이라고 생각합니다. 한번쯤 큐를 이용해

코딩을 해보시는 것도 좋을 것 같습니다.