[D2] SWEA 1945 소인수분해 - Java

SW Expert Academy

간단한 소인수분해 문제이다.

문제에서 제시된 2, 3, 5, 7, 11로 나누어 떨어지게 테스트 케이스 구성을 해 놓은 듯 하다.

 

import java.util.Scanner;

public class S_1945 {
    // 간단한 소인수분해
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] arr = {2, 3, 5, 7, 11};
        for (int i = 0; i < t; i++) { // test case
            int n = sc.nextInt();
            int[] res = new int[arr.length];

            for (int j = arr.length - 1; j >= 0; j--) {
                int cnt = 0; // 차수

                while (n % arr[j] == 0) {
                    n /= arr[j]; // 더 이상 정수로 나눌 수 없을 때 까지 나눠줌
                    cnt++; // 차수 증가
                }
                res[j] = cnt;
            }

            System.out.print("#" + (i+1) + " ");
            for (int j = 0; j < res.length; j++) {
                System.out.print(res[j] + " ");
            }
            System.out.println();
        }
    }
}

소인수분해 문제는 while문을 통해 풀어주면 간단하다.

int[] arr = {2, 3, 5, 7, 11};

문제에서 2, 3, 5, 7, 11의 소인수분해 될 숫자를 제시해주었기 때문에 먼저 배열을 만들고 활용해주었다.

int n = sc.nextInt();
int[] res = new int[arr.length];

for (int j = arr.length - 1; j >= 0; j--) {
    int cnt = 0; // 차수

    while (n % arr[j] == 0) {
        n /= arr[j]; // 더 이상 정수로 나눌 수 없을 때 까지 나눠줌
        cnt++; // 차수 증가
    }
    res[j] = cnt;
}

그 다음으로 큰 수부터 나누어야 하기 때문에 arr 배열의 역순으로 n을 나누었다.

그리고 우리가 구해야 하는 것도 2, 3, 5, 7, 11의 차수를 순서대로 출력해주어야 한다.

arr 배열에 있는 숫자를 하나씩 나누면서 cnt 변수를 더해주고, 더 이상 안나눠질 때까지 while문을 통해 반복한다.

이 과정을 통해 각각 숫자의 차수를 res 배열에 담아 출력하면 된다.

 

정말 기본적인 간단한 소인수분해 문제이다.

while문을 통해 해당 정수를 계속 나눠주고 카운트 하면 차수를 구할 수 있는 방법으로 풀었다.