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

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

9506번: 약수들의 합

 

간단한 문제지만 코드 리팩토링 연습을 위해서 다시 한번 풀어 보았어요.

쉽게 생각하면 입력 받은 수까지 반복문을 돌며 약수인지 체크하고 ArrayList에 추가하는 방법을 통해서 해결할 수도 있겠지만,

조금 더 효율적으로 해결하기 위한 방법을 생각해 봅시다 🙃

---

문제 분석

Point _1

Case 1.

주어진 수의 약수(자기 자신을 제외한)들의 합이 주어진 수와 같다면

"x = a + b + c + ... + z"

의 형태로 출력

 

Case 2.

주어진 수의 약수(자기 자신을 제외한)들의 합이 주어진 수와 다르다면

"x is NOT perfect."

의 형태로 출력

 

반복하여 " + " 문자열을 추가하는 부분은 어떻게 처리할 것 인가?

• substring
• (StringBuilder) delete
• 마지막 약수를 더 하는 시점에 " + " 반복 종료

등의 방법 중 어떤 방법을 사용할 것 인지

Point_2

Point_1 - Case 1의 경우 약수들의 합을 오름차순으로 출력해야 함

 

---

제출 코드

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

public class Main {
    private final static Set<Integer> set = new TreeSet<>();
    private final static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int target = 0;

        while ((target = Integer.parseInt(br.readLine())) != -1) {
            set.add(1);
            addDivisor(target);
            boolean equal = set.stream()
                        	.mapToInt(Integer::intValue)
                                .sum() == target;
            System.out.println(makeString(equal, target));
            set.clear();
        }
        br.close();
    }

    static void addDivisor(int target) {
        for (int i = 2; i <= Math.sqrt(target); i++) {
            if (target % i == 0) {
                set.add(i);
                set.add(target / i);
            }
        }
    }

    static String makeString(boolean equal, int target) {
        sb.setLength(0);
        
        if (equal) {
            sb.append(target).append(" = ");
            set.stream()
            	.forEach(elem -> sb.append(elem)
                .append(" + "));
            sb.delete(sb.length() - 3, sb.length());
        } else {
            sb.append(target).append(" is NOT perfect.");
        }

        return sb.toString();
    }
}

 

• 반복문을 돌 때마다 Set, StringBuilder 객체를 생성하는 것은 비효율적이라 생각하여 static으로 객체를 메모리에 할당
  → 반복문 한 cycle마다 객체 내 값 clear
• 오름차순 정렬이 필요하니TreeSet을 사용
• stream을 통해 불필요하게 길어지는 코드들을 정리
• 주어진 수의 제곱근 값까지만 반복을 통하여 탐색범위 축소

등을 고려하여 위와 같이 코드를 구성했어요!

 

질문이나 조언이 있다면 댓글로 남겨주시면 감사하겠습니다 🙇🏻‍♂️