No9020 골드바흐의 추측(우여곡절이 많았던..)

[문제]

[입력 출력 조건]

 

[수도 코드]

• 소수들의 집합을 먼저 구해야 함 -> 에라토스테네스의 체에 대해서 먼저 알아볼 필요가 있음
• 일단 먼저 소수란 1과 자기 자신만을 약수로 가지고 있는 자연수라고 할 수 있음
• 에라토스테스의 체란? 구하고자 하는 구간의 모든 자연수를 나열한 후 소수의 배수들을 전부 지워주는 방식.
  - 예를 들어 100까지의 소수를 구하고자 한다면 일단 1은 제외하고 제일 작은 값인 2를 소수로 채택 -> 2의 모든 배수들 지우기
  - 그 다음 작은 값인 3을 소수로 채택 -> 3의 모든 배수 지우기
  - 이런 식으로 배수들을 지워나가면 결국 마지막에는 소수들만 남아있음
• 에라토스테스의 체를 이용해서 소수면 false로 boolean 배열 안에 저장해놓고, 소수의 값들만 list에 저장
• list에 담겨있는 값들을 가지고 본격적으로 n의 합이 될 수 있는 소수 찾기

---

처음에 코드를 짜고 결과값이 나왔을 땐 나름 잘 짰다고 생각했는데 시간초과가 떴다.

시간초과를 해결하고 났더니 틀린 값이라는 결과가 나왔는데 찾았던 반례와 시간초과를 어떤 식으로 해결했는지를 중점적으로 적어보고자 한다.

---

[제일 처음 짰던 코드]

public class Main {

    public static void main(String[] args) {
        //골드바흐의 추측 : 2보다 큰 모든 짝수는 두 소수의 합으로 이루어져있다
        //소수를 먼저 구하기 -> 에르토스테네스의 체 : 1은 제외, 제일 작은 2를 소수로 채택 -> 2의 배수 모드 지우기,
        // 3을 소수 채택 -< 3의 배수 모두 지우기
        Scanner in = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        boolean[] flag = new boolean[0];

        int T = in.nextInt();

        for(int i=0;i<T;i++) {
            int n = in.nextInt();
//            flag = solution(n,list);
            solution(n,list);
        }
    }

    public static void solution(int n,List<Integer> list) {
        //소수구하기
        boolean flag[] = new boolean[n+1];
        int n1=0;
        int n2=0;
        int min = 10000;

        for(boolean k:flag) {
            k=false;
        }

        //소수면 false;
        flag[0]=flag[1]=true;

	//배수들은 전부 true로 바꿔주고 false면 list에 바로 저장하도록 구현
        for(int i=2;i<=n;i++) {
            if(!flag[i]) {
                for(int j=2*i;j<=n;j+=i) {
                    flag[j] = true;
                }
            }
            if(flag[i]==false) {
                list.add(i);
            }
        }

	//list에 담은 값들의 합을 구하기 시작
       	//i -> 2 j -> 2 => 2+2 
       	//i -> 2 j -> 3 => 2+3
        
        for(int i=0;i<list.size();i++) {
            for(int j=0;j<list.size();j++) {
                if(list.get(i)+list.get(j)==n) {
                    int gap = list.get(i)-list.get(j);
                    
                    // 10이란 수의 소수는 2,3,5,7이고 소수의 값의 합이 10이 나오는 조합은
                   // 3+7, 5+5, 7+3 이렇게 총 3가지가 있음
                   // 두 값의 차가 음수일 때 절대값을 만들기 위해 -1을 곱해줌
                    
                    if(gap<0) {
                        gap *= (-1);
                    }
                    if(gap<min) {
                        n1 = list.get(i);
                        n2 = list.get(j);
                        min = gap;
                    }
                }
            }
        }

        System.out.println(n1+" "+n2);

    }

}

 

일단 제일 처음엔 따로 소수를 구하는 메소드를 만들려고 했었다. 그런데 이 값을 바로바로 list에 저장하려고 했더니 값을 리턴해오는 과정에서 조금 복잡한 부분이 있어서 아예 solution 메소드에서 모든 로직을 구현하고 main에서는 테스트 케이스와 n의 값을 받아오는 과정만 진행하려고 했었다. 처음 8, 10, 16의 값을 예제로 넣었을 땐 출력이 잘 돼서 바로 제출을 했으나 시간 초과.

-> 생각한 해결 방법 : 따로 solution 메소드를 만들어서 매번 매개변수로 List를 받아오고 메소드 안에서 배열을 생성해주다보니 오히려 시간초과가 생긴것이 아닌가 싶어서 아예 main선언부로 코드들을 가지고 왔음 (지금 생각해보면 이건 그리 중요한게 아니었던 것 같음)

또한 Scanner를 이용해서 값을 받아온 부분을 Buffer와 Tokenizer를 이용해서 수정을 해줬다.

 

현재 블로그에선 코드를 생략하겠지만 이렇게 해도 여전히 시간초과가 떴고 결국 본질적인 로직이 문제라는 생각을 하게됐다.

-> 생각한 해결 방법 : 가장 잘못 생각하고 있었던 부분이 처음에 배열을 선언만해주고 for문 안에서 받아서 n의 값만큼 배열의 크기를 만들어서 소수를 걸러내는 작업을 진행했었다. n의 값이 작은 값들만 생각을 해서 오히려 처음 배열의 크기를 10001만큼 만들어주는게 더 부담일거라고 생각했는데 큰 수들이 여러번 들어왔을 때 돌아갈 반복문의 횟수를 생각해보니 그 부분이 가장 본질적인 문제였다는 생각을 하게 됐다. 따라서 처음부터 배열의 범위를 [10001]로 만들어주고 소수를 걸러내서 list에 미리 저장! 굳이 에라토스테네스의 체를 여러번 생성할 필요가 없으므로.

 

 

[수정본]

public class Main {

    public static void main(String[] args) throws Exception {
        //골드바흐의 추측 : 2보다 큰 모든 짝수는 두 소수의 합으로 이루어져있다
        //소수를 먼저 구하기 -> 에르토스테네스의 체 : 1은 제외, 제일 작은 2를 소수로 채택 -> 2의 배수 모드 지우기,
        // 3을 소수 채택 -< 3의 배수 모두 지우기

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        List<Integer> list = new ArrayList<>();
        boolean[] flag = new boolean[10001];

	//미리 소수들 걸러내기
        for (int i = 0; i < flag.length; i++) {
            flag[i] = true;
        }
        //소수면 true;
        for (int i = 2; i * i < flag.length; i++) {
            if (flag[i]) {
                for (int j = i * i; j < flag.length; j += i) {
                    flag[j] = false;
                }
            }
            if (flag[i] == true) {
                list.add(i);
            }
        }

        int T = Integer.parseInt(in.readLine());

        for (int m = 0; m < T; m++) {
            st = new StringTokenizer(in.readLine());
            int n = Integer.parseInt(st.nextToken());
            int n1 = 0;
            int n2 = 0;
            int min = 10000;
            int gap = 0;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) > n) break;
                for (int j = i; j < list.size(); j++) {
                    if (list.get(i) + list.get(j) > n) break;
                    if (list.get(i) + list.get(j) == n) {
                        n1 = list.get(i);
                        n2 = list.get(j);
                        gap = n2 - n1;
                        if(gap<0) {
                        gap *= (-1);
                    }
                    if(gap<min) {
                        n1 = list.get(i);
                        n2 = list.get(j);
                        min = gap;
                    }
                    }
                }
            }
            bw.write(n1+" "+n2+"\n");
            bw.flush();
        }
        in.close();
        bw.close();

    }
}

이제는 시간초과 문제는 해결하였으나 값이 틀렸다고 나왔다. 어디서 틀렸는지 찾아보기 위해서 일단 현재 list에 저장된 값들을 출력해보니 100 이하의 소수들만 저장이 되어있었다. 결국 소수를 걸러내는 과정에서 뭔가 잘못된 부분이 있는 것이다.

-> 생각한 해결 방법 : 어차피 boolean의 기본형은 false이므로 불필요하게 전체를 true로 초기화하는 과정을 생략하고, 소수의 배수를 찾아내는 과정에서 flag[i]가 true면 배수의 값들을 false로 바꾸는 과정에서 if문을 생략. 이후에 flag[i]가 true면 list에 add하는 코드는 결국 100번밖에 수행될 수 없으니 당연히 100 이하의 소수만 저장될 수밖에 없음

또 고민을 많이 했던 부분이 소수의 합을 구할 때 {2, 3, 5, 7} {2, 3, 5, 7} - 2,2 / 2,3 / 2,5 / 2,7 이렇게 한번 돌고난 이후 3부터 시작될 때 이미 확인을 했던 부분을 거치지 않고 3,2 (X) 3,3 (O) 바로 넘어갈 수 있는 방법을 고민을 많이 했는데 의외로 간단하게 for문의 시작범위 j를 i로 바꿔주면 되는 문제였다... 이 부분 때문에 gap의 절대값을 구해주는 코드를 구현했는데 이 문제가 해결되니 if(gap<0) 조건문은 지워도 상관이 없음!

 

[최종본]

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        List<Integer> list = new ArrayList<>();
        boolean[] flag = new boolean[10001];

        //소수면 false;
        flag[0]=flag[1]=true;
        for(int i=2; i*i<flag.length; i++){
            for(int j= i*i; j<flag.length; j+=i){ // i*i 이전값은 이미 배제된다.
                if(flag[j]==true) continue;
                else flag[j] = true;
            }
        }
        //소수만 담긴 새로운 리스트를 만든다
        for(int i=0; i<flag.length; i++){
            if(flag[i]==false) list.add(i);
        }


        int T = Integer.parseInt(in.readLine());

        for (int m = 0; m < T; m++) {
            st = new StringTokenizer(in.readLine());
            int n = Integer.parseInt(st.nextToken());
            int n1 = 0;
            int n2 = 0;
            int min = 10001;
            int gap = 0;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) > n) break;
                for (int j = i; j < list.size(); j++) {
                    if (list.get(i) + list.get(j) > n) break;
                    if (list.get(i) + list.get(j) == n) {
                        n1 = list.get(i);
                        n2 = list.get(j);
                        gap = n2 - n1;
                    if(gap<min) {
                        n1 = list.get(i);
                        n2 = list.get(j);
                        min = gap;
                    }
                    }
                }
            }
            bw.write(n1+" "+n2+"\n");
            bw.flush();
        }
        in.close();
        bw.close();

    }
}

이후에 좀 더 개선할 수 있으면 좋겠다고 생각한 부분은 굳이 min과 gap 변수를 2개나 써서 코드를 구현할 필요가 있나.. 하는 것이다. 분명 좀 더 간략한 방법이 있을 것 같은데 그 부분은 차차 생각을 해봐야 할 것 같다.

지금까지 내가 푼 문제들 중 난이도가 제일 높은 문제였는데 그만큼 시간도 오래 걸렸지만 고민했던 부분들과 개선한 부분들이 머리에서 명확하게 분리가 됐고, 이 부분을 까먹지 않기 위해서 블로그에 포스팅을 해봤다. 추가적인 설명이 필요할 것 같은 코드 리뷰나 내가 나중에 한번더 살펴보면 좋을 것 같은 부분들은 밑에 접은 글로 적어두도록 하겠다!

 

flag[0]=flag[1]=true;
for(int i=2; i*i<flag.length; i++){
    for(int j= i*i; j<flag.length; j+=i){ // i*i 이전값은 이미 배제된다.
        if(flag[j]==true) continue;
        else flag[j] = true;
    }
}

• 변수 범위 설정 추가 설명
  - 두번째 for문에서 int j = i*i와 j+=i 설명 : i가 2일 때 j는 4부터 시작해서 6, 8, 10... 2씩 증가해야 2의 배수들을 차례차례 true로 제외시킬 수 있음. 이후에 i가 3일 때는 i*i = 9부터 시작하게 되는데 굳이 3 x 2부터 시작하지 않는 이유는 이미 앞에서 2의 배수들을 제거해줬기 때문에 굳이 그 과정을 반복해줄 필요가 없음. i가 4도 마찬가지인데 4 x 2, 4 x 3의 과정은 앞에서 2와 3의 배수를 진행하면서 걸러줬기 때문에 4 x 4부터 시작을 해주는 것임! 
  - 첫번째 for문에서 i*i < flag.length 설명 : 위에 설명을 이해하면 이해할 수 있음. 100 * 100은 10000이고 마찬가지고 두번째 for문에서 차례차례 배수들을 제거해줬기 때문에 굳이 i < flag.length라고 설정해서 반복 과정을 중복해서 진행할 필요없음