[Java/백준/Bronze II] 소수 찾기 - 1978, 리팩토링(Scanner, split → BufferedReader, StringTokenizer)

성능 요약

메모리: 14152 KB, 시간: 96 ms

 

분류

소수 판정, 정수론, 수학

 

문제 설명

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

code - 1차

//문제 링크: https://www.acmicpc.net/problem/1978
//시간: 172 ms
//메모리: 17804 KB

import java.util.Scanner;
public class B1978 {
    //  소수 여부 확인
    public static boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        } else {
            for (int j=2; j<number; j++) {
                if (number % j == 0) {
                    return false;
                }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();

        String[] inputs = sc.nextLine().split(" ");
        sc.close();

        int[] numbers = new int[n]; // inputs String -> int
        int count = 0;

        for (int i=0; i<n; i++) {
            numbers[i] = Integer.parseInt(inputs[i]);
            if (isPrime(numbers[i])) {
                count++;
            }
        }
        System.out.println(count);
    }
}

🎯1차 코드에 대한 알고리즘 대장님의 피드백
1. 소수 검증 로직
: j * j <= number까지만 확인해 보아도 소수인지 확인할 수 있습니다.
만약 24가 소수인지 아닌지 검사한다면, 24는 2, 3, 4, 6, 8, 12로 나눴을 때 나머지가 0이기 때문에 소수가 아니라는 것을 알 수 있습니다. 5*5 = 25, 즉 5를 기준으로 5보다 큰 수는 이미 검증한 상태가 되는 것입니다.
2. 입력 성능 개선
: 이를 위해 BufferedReader와 StringTokenizer에 대해 공부해 보고 적용해 보기 바랍니다.

code - 2차

//문제 링크: https://www.acmicpc.net/problem/1978
//시간:  96ms
//메모리:  14152KB

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

public class B1978 {
    //  소수 여부 확인
    public static boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        } else {
            for (int j=2; j*j<=number; j++) {
                if (number % j == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();

        int count = 0;

        while (st.hasMoreTokens()) {
            int number = Integer.parseInt(st.nextToken());
            if (isPrime(number)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

🎯 피드백을 반영한 리팩토링 결과
1. 메모리 및 시간 개선
: 172 → 96ms, 17804 → 14152 KB
2. BufferedReader와 StringTokenizer를 사용하는 이유
(1) BufferedReader: 버퍼 읽기로 입출력 호출 횟수를 줄여 성능 향상, CPU와의 속도 병목을 해결합니다.
(2) StringTokenizer: 단순한 구분자로 split() 메서드보다 빠르게 파싱할 수 있습니다.

---

https://github.com/seonmin5/codingtest_Python/tree/main/%EB%B0%B1%EC%A4%80/Bronze/1978.%E2%80%85%EC%86%8C%EC%88%98%E2%80%85%EC%B0%BE%EA%B8%B0

codingtest_Python/백준/Bronze/1978. 소수 찾기 at main · seonmin5/codingtest_Python