백준 11653 소인수분해 [JAVA]

---

문제 해석

• 11653번 문제는 소인수분해 문제로, 중학교 교과 과정에 본 적이 있는 문제이다.
• 간단히 설명하자면, 정수(N)를 입력받아 소수(1을 제외한 자기 자신만으로 나누어지는 정수를 의미함)로 나눠서 0이 나오는 모든 수를 구하는 수 이다.
• 그렇게 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));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        br.close();

        if(N == 1){
            return;
        }

        for(int i = 2; i <= N; i++){
            while(N%i == 0){
                N /= i;
                sb.append(i + "\n");
            }
        }
        System.out.println(sb);
    }
}

• 위의 코드와 같이 작성하여, 맞았습니다. 를 받았다.

• 하지만 생각보다 많은 시간이 소요되어 다른 분들이 짠 코드는 어떻게 작성하였는지 궁금해졌다.
• 어떻게 하면 더 적은 시간을 사용하여 코드를 작성할 수 있을지 공부하고자 이 문제를 포스트하려한다.

효율적인 코드

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

import static java.lang.Math.sqrt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        br.close();

        //sqrt 메소드는 파라미터의 양의 제곱근을 반환
        for(int i = 2; i <= sqrt(N); i++){ //1을 제외하고
            while(N%i == 0){
                N /= i;
                sb.append(i + "\n");
            }
        }

        if(N != 1){
            sb.append(N);
        }
        System.out.println(sb);
    }
}

효율적인 코드 결과

• 소요 시간 차이가 많이 나는 것을 확인 할 수 있다.

내 코드와 다른 점

• 가장 크게 다른 점은 N의 제곱근을 사용했다는 점이다.

  72로 예시를 들자면,
  1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

• 1은 소수에 해당되지 않기때문에 1X72쌍은 제외한다.

• 그러면, 2X36, 3X24, 4X18, 6X12, 8X9과 같이 나타낼 수 있는데 한 쌍에서 인수 중 하나는 무조건 72의 제곱근인 8.4852813742386 보다 작다는 것을 알 수 있다.

• 즉, sqrt 메서드를 활용하여 N의 양의 제곱근을 구하여 N까지 반복할 필요 없이 제곱근 이하로만 반복해도 된다!
  (그 이유, N이 어떠한 수로 나눠진다는 것은 쌍을 이루는 다른 수도 포함한다는 뜻이기 때문)

• 반복문이 끝나면 소인수분해가 된 N은 1이 되어야한다.

• 하지만, 반복문이 끝나도 N이 1이 되지 않는 경우가 있다.
  - 이러한 경우는 제곱근을 쓰지 않는다면 문제가 되지 않지만, 만약 제곱근을 쓴다면 마지막 N이 1이 아닌 경우 StringBuilder에 N을 append해줘야한다.

  예시를 들자면, 46으로 들 수 있다.
  46의 제곱근은 6.78232998313 이며, 1, 2, 23, 46이다.

  • 일단, 46은 소인수가 2, 23밖에 없고, 제곱근보다 작은 것은 2밖에 없다.
  • 2로만으로 46을 만들 수 없기 때문에, 마지막에 23을 소인수로 추가해줘야한다.
  • 앞의 예시였던, 72는 소수인 2와 3으로(제곱근 8.48xxxx보다 작은) 72을 만들 수 있기 때문에 마지막에 1이 나오지만, 46은 그렇지 않다.
  • 아무튼! 34도 2와 17이므로 같은 이유로 N은 17에서 반복문이 끝날 것이고, 그렇기때문에 마지막에 N을 추가해줘야한다.

            if(N != 1){
                      sb.append(N);
                 }

느낀점

• 소인수 분해를 오랜만에 봐서, 기억이 가물가물 했었는데 알고리즘 문제로 다시 개념 정리를 했던 것 같다.
• 항상 효율적인 코드를 작성할 수 있도록 고민하고, 코드를 작성하는데 내 코드가 다른 사람의 코드보다 효율적이지 못할 때가 많고, 내가 생각해내지 못한 부분이 많아서 어렵다고 느꼈다.