백준 암호 키

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에는 수의 개수 N ()이 주어진다.
둘째 줄부터 N개의 줄에 걸쳐 확인하고자 하는 수 S가 한 줄에 하나씩 주어진다.
N개의 줄에 걸쳐,
입력받은 수가 적절한 암호 키이면 YES,
아니면 NO를 순서대로 출력한다.

내가 이 문제를 보고 생각해본 부분

첫번째 코드를 작성해보고 시간초과가 나와서 고심끝에 두번째 코드를 작성해봤다.
이중for문 if-else문을 사용해서 간단하게 마무리 했다.

코드로 구현

package baekjoon.baekjoon_23;

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

// 백준 1816번 문제
public class Main800 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            long S = Long.parseLong(br.readLine());
            if (isValidKey(S)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        br.close();
    }

    // 주어진 S가 적절한 암호 키인지 확인하는 메소드
    private static boolean isValidKey(long S) {
        // 10^6 = 1000000
        long limit = 1000000;

        // 2부터 limit까지의 수로 S를 나누어 소인수를 찾는다.
        for (long i = 2; i * i <= S; i++) {
            if (S % i == 0) {
                // 소인수를 찾으면, 해당 소인수가 limit 이하인지 확인
                if (i <= limit) {
                    return false; // 적절하지 않은 암호 키
                }
                // 소인수 i로 나눈 후 S를 갱신
                while (S % i == 0) {
                    S /= i;
                }
            }
        }

        // 나머지 S가 1보다 크고 limit 이하인지 확인
        return S > limit || S == 1; // S가 소수이고 10^6보다 크면 적절한 키
    }
}

package baekjoon.baekjoon_23;

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

// 백준 1816번 문제
public class Main800 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++) {
            long num = Long.parseLong(br.readLine());
            for(int j = 2; j <= 1000000; j++) {
                if(num %j == 0) {
                    System.out.println("NO");
                    break;
                } else if(j == 1000000) {
                    System.out.println("YES");
                }
            }
        }
        br.close();
    }
}

재귀함수를 사용해서 시간초과가 나오는것같았다. 그래서 코드를 다시 작성해봤다.
그래서 코드를 이중 for문과 if - else 문으로 바꿔줘서 문제를 풀었다.

첫 번째 코드의 시간 복잡도는 O(N × 10^6)로, ( N )이 커질 경우 매우 느릴 수 있다.
두 번째 코드의 시간 복잡도는 O(N × √S)로, ( S )가 큰 경우에도 상대적으로 빠르다.

처음에 어떤 부분이 문제인지 조금 감이안왔다. chatgpt에게 두 코드를 주고 시간의 복잡도를 비교해봤다.
두 번째 코드가 더 효율적인 이유는 ( S )의 제곱근까지만 검사하므로, 첫 번째 코드보다 더 빠르게 실행될 수 있기 때문이라는 답변을 받았다.

재귀함수가 더 빠를줄 알았는데 내가 알고있는게 전부는 아니였던것같다.

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.