자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_뒤집은 소수)

https://cote.inflearn.com/contest/10/problem/02-06

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

 

6. 뒤집은 소수

 

예시 입력 1 

9
32 55 62 20 250 370 200 30 100

예시 출력 1

23 2 73 2 3

 

내가 푼 풀이(Time: 172ms Memory: 27MB)

1. 입력된 int[]를  자리수를 계산하면서 전부 뒤집는다.

2. checkPrime함수를 통해 소수인것만 String으로 리턴한다

3. isPrime함수를 통해 소수인 것만 true로 체크한다.

import java.util.Scanner;

public class Main {
    // 소수인 것만 String으로 반환한다.
    public String checkPrime(int[] array) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            int num = array[i];
            if (isPrime(num)) {
                sb.append(num).append(" ");
            }
        }
        return sb.toString().trim(); // 불필요한 공백 제거
    }

    // 소수인지를 체크하는 함수
    public boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public String solution(int n, int[] array) {
        // 입력된 int[]의 값을 전부 뒤집는다.
        for (int i = 0; i < n; i++) {
            int reverse = 0;
            while (array[i] != 0) {
                reverse = reverse * 10 + array[i] % 10;
                array[i] /= 10;
            }
            array[i] = reverse;
        }
        return checkPrime(array);
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        System.out.println(T.solution(n, array));
    }
}

 

isPrime함수 속 조건 문이 i <= num가 아니라 i * i <= num인 이유?

`i * i <= num` 조건문을 사용하는 이유는 소수 판별을 더 효율적으로 수행하기 위해서입니다. 이 조건문을 사용하면 반복 횟수를 줄일 수 있습니다. 첫 번째 코드와 두 번째 코드의 성능 차이는 주로 소수 판별에서 발생합니다.

첫 번째 코드(i * i <= num)에서는 `i * i <= num` 조건문을 사용하여 소수를 판별합니다. 이 조건문은 `num`의 제곱근 이하의 수로만 나눗셈을 수행하므로 반복 횟수가 적어지고 더 효율적입니다. 이것이 일반적으로 빠른 이유입니다.num의 제곱근 이하의 수로만 나눗셈을 수행하므로 나눗셈 연산의 수가 크게 줄어들어 성능이 향상됩니다. 주요 병목을 해소하여 코드를 최적화할 수 있는 것이죠.

예를 들어, 16이 소수인지 판별하려고 할 때, `i * i <= num` 조건문을 사용한다면 다음과 같이 동작합니다:

1. i = 2에서 시작하여 i * i가 16보다 작거나 같을 때까지 반복
2. i = 2, 3, 4까지 총 3번 반복
3. 각 반복에서 `num % i == 0`을 체크하여 소수 여부를 판별

이런 방식으로 3번의 반복만 수행합니다. 

두 번째 코드(i <= num)에서는 `i < num` 조건문을 사용하여 소수를 판별합니다. 이 경우 `num`까지 모든 수로 나눗셈을 수행하므로 반복 횟수가 많아집니다. 그러므로 더 많은 나눗셈 연산이 필요하고 시간이 더 오래 걸립니다. 

그러나 `i <= num` 조건문을 사용한다면 다음과 같이 동작합니다:

1. i = 2에서 시작하여 i가 16보다 작거나 같을 때까지 반복
2. i = 2, 3, 4, ..., 16까지 총 15번 반복
3. 각 반복에서 `num % i == 0`을 체크하여 소수 여부를 판별

이런 방식으로 15번의 반복을 수행합니다. 

두 코드 모두 소수를 판별하는 데 사용되는 나눗셈 연산이 주요 병목(bottleneck)입니다. 따라서 첫 번째 코드가 일반적으로 더 효율적입니다. 

또한, 코드의 실행 속도는 여러 요소에 영향을 받을 수 있으며, 컴파일러나 JVM(Java Virtual Machine)의 최적화도 영향을 미칠 수 있으므로 코드 실행 시간의 차이는 환경에 따라 다를 수 있습니다.

 

"주요 병목(bottleneck)"이란 프로그램 또는 코드의 실행 중에서 가장 시간이 많이 소요되는 부분을 가리키는 용어입니다. 이 부분은 프로그램의 전체 실행 시간에 가장 큰 영향을 미치는 부분이며, 프로그램의 성능을 결정하는 핵심적인 요소입니다. 따라서 주요 병목은 프로그램을 최적화하거나 개선하는 데 중요한 곳입니다.

 

소수 판별 코드에서의 주요 병목은 일반적으로 소수를 판별하는 부분인 나눗셈 연산입니다. 소수를 판별할 때, 모든 수로 나눗셈을 수행하여 소수인지 아닌지 확인합니다. 여기서 나눗셈 연산이 시간을 많이 소모하는 작업 중 하나입니다.

제곱근은 어떤 숫자를 제곱했을 때 원래의 숫자가 되는 수를 의미합니다. 예를 들어:

- 9의 제곱근은 3입니다. 왜냐하면 3을 제곱하면 9가 됩니다 (3 * 3 = 9).
- 25의 제곱근은 5입니다. 왜냐하면 5를 제곱하면 25가 됩니다 (5 * 5 = 25).

그러면 "i * i <= num" 조건문을 예시를 통해 설명해보겠습니다. 예를 들어, 우리가 16이라는 숫자를 소수인지 판별하려고 한다고 가정합시다. 이때 "i * i <= num" 조건문은 다음과 같이 동작합니다:

1. i를 2로 초기화합니다.
2. i * i를 계산하면 2 * 2 = 4가 됩니다. 이때 4는 16보다 작거나 같으므로 이 조건을 만족합니다.
3. 다음으로 i를 3으로 업데이트하고 다시 i * i를 계산하면 3 * 3 = 9가 됩니다. 9도 16보다 작거나 같으므로 이 조건을 만족합니다.
4. i를 4로 업데이트하고 i * i를 계산하면 4 * 4 = 16이 됩니다. 16은 16과 같으므로 여전히 이 조건을 만족합니다.
5. 그러나 i를 5로 업데이트하고 i * i를 계산하면 5 * 5 = 25가 됩니다. 25는 16보다 크므로 조건을 만족하지 않습니다.

즉, "i * i <= num" 조건문은 i를 2부터 시작하여 i * i가 num보다 작거나 같을 때까지 i를 증가시키는 역할을 합니다. 이 조건을 만족하지 않으면 루프를 종료하고, 이때까지 나누어 떨어지지 않았다면 해당 숫자는 소수로 간주합니다.

출력값으로 확실히 알아보자

        // 약수를 체크
        for (int i = 2; i * i <= num; i++) {
            System.out.println("num : " + num);
            System.out.println("i : " + i);
            if (num % i == 0) {
                System.out.println("false");
                return false;
            }
        }

num : 23
i : 2
num : 23
i : 3
num : 23
i : 4
true
num : 55
i : 2
num : 55
i : 3
num : 55
i : 4
num : 55
i : 5
false
num : 26
i : 2
false
true
num : 52
i : 2
false
num : 73
i : 2
num : 73
i : 3
num : 73
i : 4
num : 73
i : 5
num : 73
i : 6
num : 73
i : 7
num : 73
i : 8
true
true
true

 

 

강의 풀이 (Time: 178ms Memory: 27MB)

1. 각각의 숫자들을 하나씩 탐색해야하기 때문에 0부터 for문을 돌린다.

2. 각 숫자들을 자릿수 계산해서 뒤집어 준다.

3. isPrime함수를 통해 매개변수로 들어오는 숫자가 소수인지 확인한다

     3-1. 2부터 해당 숫자까지 약수가 발생하면 false 아니면 true

     3-2. num이 2일 경우, 조건문이 i < num이기 때문에 truef로 반환된다.

import java.util.ArrayList;
import java.util.Scanner;

public class Answer {

    public boolean isPrime(int num ){
        // 1은 소수가 아니다
        if (num == 1) return false;
        for (int i = 2; i < num; i++) {
            // i가 num의 약수가 되는 경우
            if (num % i == 0) return false;
        }
        return true;
    }

    public ArrayList<Integer> solution(int n, int[] arr) {

        ArrayList<Integer> answer = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int tmp = arr[i];
            int res = 0;
            while(tmp > 0) {
                int t = tmp % 10;
                res = res * 10 + t;
                tmp = tmp /10;
            }
            if (isPrime(res)) answer.add(res);
        }
        return answer;
    }

    public static void main(String[] args) {
        Answer T = new Answer();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int x : T.solution(n, arr)) {
            System.out.print(x+ " ");
        }
    }
}

 

 

참고 링크 :

https://rypro.tistory.com/215

[Java] 숫자 뒤집기