[051] 6588. 골드바흐의 추측

✨ 알고리즘 분류 : 수학 / 정수론 / 소수 판정 / 에라토스테네스의 제

 

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 짝수를 두 개의 소수 합으로 계산해 출력한다.

- b - a가 가장 큰 것을 출력한다 (a가 제일 작은 것을 출력한다)

- 소수 합에서의 각각 소수는 홀수이다

- n은 6 이상 1,000,000 이하의 자연수이다.

 

 

 

🧶 풀이과정 

 

이건 이전에 소수 구하기에서 내가 따악! 운이 좋게! 리스트를 활용하는 덕에 아주 쉽게 풀 수 있었다.

 

2024.04.05 - [Algorithm] - [050] 1929. 소수 구하기

[050] 1929. 소수 구하기

 

만약 리스트를 활용 안 했다? 그럼 좀 오래 걸렸겠지.

전반적으로는 이 코드와 비슷하다. 우선 풀이를 설명하자면 다음과 같다.

 

1. primes에 3부터 1,000,000 까지의 홀수 중 소수를 판별하여 넣는다. 

2. n이 들어오면, primes의 첫번째부터 (첫번째는 3이다)  primes.size/2 +1 까지 순회한다.

*** primes/2+1 인 이유는 그것을 넘어가면 결국 역순 순회와 같아지기 때문!!!

3. n - primes[i] 가 primes에 존재한다면, 그것은 소수의 합이므로 출력하고 반복을 종료한다.

4. 만약 반복문의 끝에 도달했을 때에 답이 존재하지 않는다면 " Goldbach's conjecture is wrong." 을 출력한다.

 

이와 같은 과정을 거치게 되는데, 처음에는 시간 초과가 났다.

import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main{

    static List<Integer> primes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        primes.add(3);

        for(int i = 1; i < 1000000; i += 2){

            if(primeCk(i)){
                primes.add(i);
               // System.out.println(i);
            }
        }

        int n;

        while((n = Integer.parseInt(br.readLine())) != 0){


            int halfSize = primes.size()/2 + 1;
            for(int i = 0; i < halfSize; i++){
                int fst = primes.get(i);
                int last = n - primes.get(i);

                if(primes.contains(last)){
                    System.out.println(n + " = " + fst + " + " + last);
                    break;
                }

                if(i == halfSize -1){
                    System.out.println("Goldbach's conjecture is wrong.");
                }
            }

        }


        
        br.close();
    }

    public static boolean primeCk(int num){

        if(num <= 2) return false;

        for(int i = 0; primes.get(i) * primes.get(i) <= num; i++){

            if(num % primes.get(i) == 0){
                return false;
            }
        }

        return true;
    }


}

 

 

왜 문제가 되는지 한참 살펴보는데, List의 contains 때문이었다. 리스트는 순서가 존재하는 것이라, 특정한 값을 찾으려면 값을 순회해서 찾게 된다. 그러

므로 시간복잡도가 O(n) 이 된다. 현재 리스트 안에는 많은 것이 담겨있어서 이와 같을 때에 적합하지 않은 것이다.

 

그래서 다음으로는 Set을 생각했다. list는 그대로 두고, 검색만 하면 되니까 그때는 set을 사용하는 것이다.

 

Set의 경우 순서가 존재하지 않고 키 값으로 구분하는데, 해시 테이블을 사용하기 때문에 주소값으로 빠르게 찾아갈 수 있다. 순회를 하는 것이 아니므로 검색을 할 때 시간복잡도가 O(1)로, 길이에 무관한 속도를 가지기에 단순히 값을 찾는 현재 코드에서 아주 유용하게 쓰일 것 같았다.

 

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

public class Q6588 {

    static long startTime = System.currentTimeMillis();
    static List<Integer> primes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        primes.add(3);

        for(int i = 1; i < 1000000; i += 2){

            if(primeCk(i)){
                primes.add(i);
               // System.out.println(i);
            }
        }

        int n;
        Set<Integer> pSet = new HashSet<>(primes);

        while((n = Integer.parseInt(br.readLine())) != 0){


            int halfSize = primes.size()/2 + 1;
            for(int i = 0; i < halfSize; i++){
                int fst = primes.get(i);
                int last = n - primes.get(i);

                if(pSet.contains(last)){
                    System.out.println(n + " = " + fst + " + " + last);
                    break;
                }

                if(i == halfSize -1){
                    System.out.println("Goldbach's conjecture is wrong.");
                }
            }

        }

        long endTime = System.currentTimeMillis();
        long exTime = endTime - startTime;

        System.out.println(exTime + "ms 걸림");

        br.close();
    }

    public static boolean primeCk(int num){

        if(num <= 2) return false;

        for(int i = 0; primes.get(i) * primes.get(i) <= num; i++){

            if(num % primes.get(i) == 0){
                return false;
            }
        }

        return true;
    }


}