개요

백준 단계별로 풀어보기 <약수, 배수와 소수> 3단계 문제인 "약수들의 합" 문제를 풀어보자.

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

---

문제

문제는 간단하다.
자신의 약수들의 총합을 모두 더한 값이 자신과 같은 수를 완전수라고 하며, input이 완전수인지 아닌지를 판별하는 프로그램을 구현하는 것이다.

---

설계

일단 나는 저 예제 출력 화면에서 약수의 출력을 오름차순하는 것을 보고 큐를 사용해야겠다는 생각이 들었다.
자바에서 큐를 사용해본 적이 없어서 우선 이 문제를 위한 큐의 사용법을 간단하게 학습했다.

---

큐

import java.util.LinkedList;
import java.util.Queue;
Queue<Integer> queue = new LinkedList<>();	//int형
queue.add(23);	// 원소 추가
queue.peek();	// 원소 리턴 (참조만)
queue.poll();	// 맨 앞 원소 pop(리턴 및 삭제)

자바에서 큐는 Linkedlist를 활용해서 생성해야 한다. 그렇기에 Queue와 Linkedlist 둘 다 import 되어 있어야 사용 가능하다.
Queue<Element> queue = new LinkedList<>() 와 같이 선언해주면 된다.

큐에 원소를 추가할 때는 linked list처럼 .add()메소드를 사용하며,
stack이랑 다르게 원소를 빼낼 때는 pop이 아닌 poll() 메소드를 사용한다.

peek() 메소드와 poll() 메소드의 차이에 주의하자. pekk() 메소드는 원소를 단순 참조해서 리턴만 하기 때문에 큐에서 원소를 삭제하지는 않는다.
반면 poll() 메소드는 FIFO(선입선출)에 따라 큐에서 실제로 원소를 뱉어내므로 원소가 삭제된다.

---

약수들을 큐에 넣고, if문으로 큐의 모든 원소의 합이 n과 같은지를 판별하면 될 것 같다.

---

구현

일단 n의 약수를 찾아야 한다. 단, 약수들 중에서 n 자기 자신은 제외돼야 하므로 for문에서 i가 n을 포함하지 않고, i=1부터 i < n까지만 반복된다.
if 그 약수들을 다 더한 sum 값이 n과 같다면 큐에서 값을 하나씩 빼내어 오름차순으로 답을 출력하고,
else 완전수가 아님을 출력한다.

package CThree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = -1;
        int sum = 0;
        Queue<Integer> queue = new LinkedList<>();

        while (true) {
            n = scanner.nextInt();
            if (n == -1) {
                break;
            }

            sum = 0;

            for (int i = 1; i < n; i++) {
                if (n % i == 0) {
                    queue.add(i);
                    sum += i;
                }
            }

            if (sum == n) {
                System.out.print(n + " = " + queue.poll());
                while (!queue.isEmpty()) {
                    System.out.print(" + " + queue.poll());
                }
                System.out.println();
            }

            else {
                System.out.println(n + " is NOT perfect.");
            }
        }
    }
}

코드를 구현하여 제출해보자.

(blob:https://velog.io/49fbcf29-fe00-4388-aee1-824657508195)

실패가 떴다.

6, 12, 28 순서로 예제를 로컬에서 입력해보니 28의 출력 순서가 이상했다.
그렇다. 12의 약수들이 큐에 그대로 들어있는 것이었다.
if문에서는 큐의 값들이 출력되면서 큐를 비우니까 큐의 초기화를 안 해도 되지만, else에서는 그렇지 않으므로 다음 반복문이 큐가 깨끗한 상태에서 시작하렴녀 큐를 비워주는 코드가 있어야 한다. 이 부분을 놓쳤던 것이다.

queue.clear();	// 큐 비우기 (원소 모두 삭제)

else 문에 해당 코드 한 줄만 끼워 넣으면 된다.

전체 완성 코드는 다음과 같다.

package CThree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = -1;
        int sum = 0;
        Queue<Integer> queue = new LinkedList<>();

        while (true) {
            n = scanner.nextInt();
            if (n == -1) {
                break;
            }

            sum = 0;

            for (int i = 1; i < n; i++) {
                if (n % i == 0) {
                    queue.add(i);
                    sum += i;
                }
            }

            if (sum == n) {
                System.out.print(n + " = " + queue.poll());
                while (!queue.isEmpty()) {
                    System.out.print(" + " + queue.poll());
                }
                System.out.println();
            }

            else {
                queue.clear();
                System.out.println(n + " is NOT perfect.");
            }
        }
    }
}

성공했다!