태화의 일기장

1. 문제 번호 1978번

2. 문제 풀이

한줄 평가

•   특히나 배열의 index는 너무 헷갈리게 한다.
•   처음에 잘못 설계한 탓에 2시간 넘게 ..걸렸다.
  
  • 입력받은 1 3 5 7을 7까지 true,false로 초판 초기화하여 진행하려다가 맨 마지막에 잘못됨을 깨달았다.
• continue는 아래를 실행하는게 아니라 for문을 다시 실행 (당연하지만 실수를 했다.)

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

   2시간 짜리 헛고생을 지독하게 했다.

1. 1 3 5 7 을 배열 index 1 ~4까지 넣었다. ( ..?? 왜 그랬지.. 0에 다가 안넣으려고 별 짓을 다했다.)
2. 7까지 8자리 인덱스 배열에 boolean으로 다 만들었다.
3. 에라토스테네스 체를 사용
4. 남은것을 출력 ( 2 3 5 7 이 출력되버림..ㅡㅡ 2는 입력을 받지 않았으니 출력되면 안됐었다..)

3. 소스 인증

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int isPrimeCnt = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            boolean isPrimeYn = false;
            isPrimeYn = isPrime(Integer.parseInt(st.nextToken()));
            if(isPrimeYn) {
                isPrimeCnt++;
            }
        }
        System.out.println(isPrimeCnt);
        
    }
    public static boolean isPrime(int inputNum){
        if(inputNum < 2) return false;
        
        int end = (int)Math.sqrt(inputNum);
        for(int i = 2; i <= end; i++){
            if( (inputNum % i) == 0) {
                return false;
            }
        }
        return true;
    }
}

import java.util.*;
import java.lang.*;
import java.io.*;

/*
이 방법은 쓰지마세요 ㅋㅋㅋ
나의 문제풀이 방식 및 순서 보시면 잘못된 설계가 결과도 이상하게 만듭니다..
*/
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int inputCnt = Integer.parseInt(br.readLine());
        int [] inputAry = new int[inputCnt];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < inputCnt; i++) {
            inputAry[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(inputAry);
        primeNumberSieve(inputAry);
    }
    
    static void primeNumberSieve(int[] inputAry){
        // int maxValue = inputAry[inputAry.length-1];
        int maxValue = Arrays.stream(inputAry).max().getAsInt();
        
        boolean[] isPrime = new boolean[maxValue+1];
        Arrays.fill(isPrime,true); //모두 소수로 초기화
        isPrime[0] = isPrime[1] = false;
        
        /*에라토스테네스 체 사용*/
        for(int i = 2; i <= Math.sqrt(maxValue); i++){
            if(isPrime[i]){ //continue; //이미 지워진 숫자는 무시
                for(int j = i*i; j <= maxValue; j += i){ //배수는 삭제
                    isPrime[j] = false;
                }
            } 
        }

        int countPrimeNumber = 0;
        // for(int i = 0; i < isPrime.length; i++){
        //     if(isPrime[i]){
        //         countPrimeNumber++;    
        //     }
        // }
        for(int num : inputAry) {
            if(isPrime[num]) {
                countPrimeNumber++;
            }
        }

        
        System.out.print(countPrimeNumber);
        
    }
}

- 실패 소스코드 -

4.추가 개념

에라토스테네스의 체

• 개념 : 여러개의 소수를 한 꺼번에 판별하고자 할 때 사용

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(57));
    }
    static boolean isPrimeNumber(int i){
        for(int j = 2; j < i; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

소수를 판별하기 위해 제일 간단하게 생각할 수 있는 소수 판별 알고리즘이다. 다만 for문을 2부터 n-1까지 모두 순차적으로 돌아야 하기 때문에  O(N)의 시간 복잡도를 가져 비효율 적이다. (앞선 알고리즘을 전부다 이렇게 풀었기 때문에 이제는 동영상 강의를 들어야 할 것 같다고 생각이 듬)

사실은  \(O(N\tfrac{1}{2})\)로 해결할 수 있다.

 소수는 1,2,3,5,7,11 과 같이 "1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수' 이다.

모든 약수는 대칭형태이다.

예를 들어 A가 12 일 때 A = 2×6, 3×4, 4×3, 6×2인데 √12 = 3.46 정도가 되므로 2~3까지만 확인 해보면 된다.

아래와 같이 참조하여 \(O(N\tfrac{1}{2})\) 로 계산이 가능하다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(97));
    }
    static boolean isPrimeNumber(int i){
        int end = (int)Math.sqrt(i);
        for(int j = 2; j <= end; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

그렇다면 왜 에라토스테네스의 체를 배우는가?

이유는 여러 개의 소수를 한꺼번에 판별하고자 할때 사용하기 위해서 사용한다.

1.  시작부터 끝까지 배열을 만든다. (2~N까지)
2.  먼저 2의 배수를 지우며 본인은 Skip한다.
3.  3의 배수를 지우며 본인은 Skip한다.
4.  5의 배수를 지우며 보인은 Skip한다. (이미 4는 지웠기 때문에 건너뛴다.)

5. 참조 블로그

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.