[5회차] 1920번 문제: 골드바흐의 추측

어제부터 생각을 곰곰히 했던 코드가 작동이 잘 되지만 결국은 시간 초과로 통과하지 못했다.

그래서 다른 분의 알고리즘을 보고 참고했다. 확실히, 내가 풀고나서 본 다른사람의 코드와 그냥 본 다른사람의 코드는 다르다. 나는 이렇게 복잡하게 생각했는데, 남들은 이렇게 쉽게 생각하다니. 더군다나 내 코드랑 다른 사람의 코드는 길이부터 차이났다. 이중 포문이 문제였기 보다는 그냥 코드 길이도 복잡하고 길어서 그랬나보다. 뭔가 딱 보면 시간 초과가 이해되기는 한다..

 

내 코드는 아래와 같았다.

import java.util.*;
import java.util.stream.IntStream;
 
public class Main {
    public static void main(String args[]){
        
        int checkIndex[] = new int[10001];
        for(int a=0; a<10001; a++) { //-1을 모두 기본적으로 삽입하기
            checkIndex[a] = -1;
        }
        
        Scanner scan = new Scanner(System.in);
        int roop = scan.nextInt(); //반복할 횟수
        String userNum[] = new String[10001];
        String thisFinal[] = new String[roop];
        int fristScan[] = new int[roop];
        
        int index = 0;
        int finalIndex = 0;
        int userNumCheck = 0;
        int done = 0;
        
        int mill[] = new int[1001];
        mill = returnPrime(); //만까지의 소수를 다 구해서 저장
        
        for(int i=0; i<roop; i++) { //횟수만큼 반복해서 숫자 넣기
            userNumCheck = scan.nextInt();
            if(userNumCheck<4) {
                System.out.println("try again");
                userNumCheck = scan.nextInt();
            }else {
                fristScan[i] = userNumCheck;
            }
        }
            
        while(done != roop) {
                //입력받은 숫자를 처리할 수 있을 때
                for(int k=0; k<mill.length; k++) {
                    //10000까지의 소수 배열 안에서 작은수 부터 하나씩 •
                    //그 수가 소수인지 아닌지를 판단
                    if(fristScan[done]<=mill[k]) { //mill 배열 안의 소수값이 기존의 소수값보다 더 클 경우
                        break;
                    } else {
                         //입력값-소수=소수일경우
                        int checkThis = fristScan[done]-mill[k];
                        boolean contains = IntStream.of(mill).anyMatch(x -> x == checkThis);    
                        if(contains == true) { //소수가 그 배열에 있다는 뜻
                            userNum[index] = mill[k] + " " + checkThis;
                            checkIndex[index] = checkThis - mill[k];
                            if(checkIndex[index]<0) { //음수이면
                                //차이가 가장 적게 나는 것을 출력하기 위해 차이를 넣는 배열 따로 선언
                                checkIndex[index] = checkIndex[index]*-1;
                            }
                            ++index;    
                            
                        }
                        
                    }
                }    
                    int thisMin = minIndex(checkIndex); //최소값이 들어있는 인덱스
                    thisFinal[finalIndex] = userNum[thisMin];
                    index = 0;
                    finalIndex++;
                    ++done;
            }
        
        for(int i=0; i<roop; i++) {
            System.out.println(thisFinal[i]);
        }
    }
 
    public static int minIndex(int[] array) { //최소값 찾는 함수
        int min = array[0];
        int minIndex = 0;
        for(int i=0; i<array.length; i++) {
            if(array[i] == -1) {
                break;
            }else if(min > array[i]) {
                min = array[i];
                minIndex = i;
            } else if(min == array[i]) {
                //아무 동작도 하지 않음
                }
            }
        //System.out.println(minIndex);
        return minIndex;
    }
    
    public static int[] returnPrime() {
        boolean isPrime[] = new boolean[10001];
        
        isPrime[0] = isPrime[1] = false;
        
        for(int i=2; i<=10000; i++) {
            isPrime[i] = true;
        }
        
        for(int i=2; i*i<=10000; i++) {
            int index = 2;
            if(isPrime[i]) {
                for(int j=i*index; j<=10000; j=i*index) {
                    isPrime[j] = false;
                    index++;
                }
            }
        }
        int thisPrime[] = new int[10001];
        int thisIndex = 0;
        for(int i=2; i<=10000; i++) {
            if(isPrime[i]) {
                thisPrime[thisIndex] = i;
                thisIndex++;
            }
        }
        return thisPrime;
    }
}

나는 그냥, 기존에 있던 원리를 응용할 생각을 안하고 그대로 그것을 함수화해서 가져다 쓸 생각만을 했다. 이제 생각하니 너무 어리석기도 하다.. 내가 생각한 알고리즘은 다음과 같았다.

 

1. 먼저 소수를 찾는 함수를 만들어 10000까지의 소수를 모두 찾아서 배열에 넣는다.

2. 그다음 몇 번 입력을 받을 것인지 입력받고, 그에 맞춰서 배열을 만들어 그 안에 입력 값들을 넣는다.

3. 입력값을 받은 배열의 인덱스를 하나하나 참조하여 그 값을 하나씩 기존의 소수 배열과 빼고 비교해가며 소수로 나올 수 있는 경우의 수를 모두 구해 다른 배열에 넣는다.

4. 그리고 그 값들의 배열의 차이를 담는 배열을 하나 만들어 그 배열 중에서 작은 값을 가지고 있는 인덱스 값을 구한다.

5. 그 인덱스 값을 가진 String 배열을 참조해 올바른 소수의 덧셈 식을 구한다.

 

였다. 지금 이렇게 써놓고 보니 너무 복잡하기 그지없다. 다음은 다른 분의 블로그를 참고하여 써봤다.

그냥 말 그대로 나에게는 신세계였다.. 이런 방법도 있구나 싶었다. 내 머리는 아직 멀었나보다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class P_9020_new {
    static StringTokenizer st;
    public static void main(String args[]) throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         st = new StringTokenizer(br.readLine());
         int T = Integer.parseInt(st.nextToken());
         
         boolean[] findingPrimeNum = new boolean[5082];
         Arrays.fill(findingPrimeNum, true);
         //모두 true로 채우고
         findingPrimeNum[0] = false;
         findingPrimeNum[1] = false;
         
         //에라토스테네스의 체 구현
         for(int i=2; i*i<=5081; i++) {
             if(findingPrimeNum[i]) {
                 for(int j=i*i; j<5081; j+=i) {
                     findingPrimeNum[j] = false;
                 }
             }
         }
         //입력된 숫자를 반으로 나눈 뒤, 출력될 왼쪽의 수는 --, 오른쪽 수는 ++ 해주면서 동시에 소수가 나오면 추측 조건에 만족한다
         //이를 이용해 코딩
         for(int t=0; t<T; t++) {
             st = new StringTokenizer(br.readLine());
             int giveNum = Integer.parseInt(st.nextToken()); //횟수만큼 받기
             int fristPartian = giveNum/2; //왼쪽 수 
             int secondPartian = giveNum/2; //오른쪽 수
             
             while(true) {
                 if(findingPrimeNum[fristPartian] && findingPrimeNum[secondPartian]) {
                     break;
                 }
                 //조건에 부합하지 않으면
                 fristPartian--;
                 secondPartian++;
             }
             bw.write(fristPartian + " " + secondPartian+"\n");
         }
         bw.flush();
    }
 
}

내 알고리즘과 달리 너무 간결해서 놀라웠다. 이 분의 코드의 알고리즘은 아래와 같다.

기본적으로 에라토스테네스의 체를 구현하여 실행한 것이다.

이것들을 다 더하면 5082개가 나온다는 결론에 다다라 boolean 타입 배열을 5082개로 설정했다고 한다.

 

1. 기본적으로 쓰일 boolean 배열을 만든다.

2. Arrays.fill(함수 이름 , 채울 내용)

이 함수를 사용하여 기본값을 true로 세팅해준다. 그리고 인덱스 0과 1은 소수에 속하지 않으므로 제외시킨다.

3. 그리고 나머지 배수들을 배제시켜줌으로써 소수들을 먼저 구해놓는다.

4. 아까 몇 번 입력할지 받았던 숫자만큼 숫자를 입력받고, 차레대로 처리에 들어간다.

5. 우선, 받은 수를 반으로 나눈다. (왼쪽 오른쪽으로 구분될 수 있게 변수를 지정해준다.)

6. 그리고 나서 조건이 true가 되면 빠져나올 수 있는 while문을 선언하는데,

이때의 조건은, 반으로 나눈 인덱스, 즉 이 수들이 소수인지 아닌지 판별하게 된다. 

아까 구했던 소수 배열에 이 숫자들의 인덱스를 넣음으로써 소수인지 아닌지 판별할 수 있게 된다.

이 인덱스의 값이 false true밖에 없기 때문에, true true는 true이므로 둘다 소수가 되어야만 while문이 종료되면서 결과가 나오게 된다.

7. 결과가 부합할때까지 왼쪽 수를 빼고, 오른쪽 수를 더함으로써 최적화 된 값을 찾을 수 있다.

 

사실, 뭔가 buffer Reader Writer는 아직도 생소하다. sysout이 너무 편한 나머지 잘 안쓰고 있기는 하지만..

앞으로 애용해볼 예정이다. 아무튼, 다른 분들의 코드를 참고하는 것도 매우 도움이 된다. 생각을 많이 해봐야겠다.