P-coding

Integer와 Int 같은 정수형을 나타내는 자료형으로 볼 수 있다.
하지만 이는 객체와 기본형으로 다르게 같지만서도 다르다.
이번에는 그 차이를 알아보자.

1. primitive type ( 기본형 )

• 값 자체를 스택 메모리에 직접 저장하는 Primitive 즉, 원시적인 자료형이다. 
• 별도의 정의가 필요없이 사용할 수 있으며 고정된 크기를 차지한다.
• 메소드를 사용할 수 없으며 값을 직접 저장하기 때문에 null 을 저장할 수 없습니다.

2. Wrapper Class ( 객체형 )

• 값은 힙 메모리에 객체에 저장되고, 스택 메모리는 그 객체를 가리키는 주소값을 저장한다.
• 참조형 데이터이기 때문에 추가적인 메모리가 소모된다.
• 기본 상태는 null로 초기화 된다.

3. 메모리 구조 예시 ( 정수 )

다음과 같은 코드를 적용할 때 그림과 같이 메모리에 할당된다.

int num = 10;
Integer num = Integer.valueOf(num);

차이점 요약

Wrapper Class는 제네릭 형태로 자주 사용되며,
특히 List<Integer> 와 같은 컬렉션 프레임워크에서 흔히 활용된다.
간단한 코드에서는 당연하게 사용하지만,
방대한 코드 작성 시에는 메모리나 성능, 기능적 요소를 고려해야 한다.
이러한 상황에 닥쳤을 때 비로소 이유를 고민하기보다, 미리 원리를 이해하고 사용하면 더 효율적일 것이다.

이번 글에서는 백준 17103번 문제를 통해 소수 찾기 알고리즘인 에라토스테네스의 체를 활용,
이를 통해 소수를 찾고 짝수를 소수의 합으로 나타내보자.

---

문제 핵심

• N : 짝수
  • 2 < N <= 1,000,000
• 두 개의 소수의 합이다.
• 순서만 다른 것은 같은 파티션이다.

풀이 과정

다음 문제는 소수를 먼저 찾아서 합을 구하면된다.

즉, 에라토스테네스의 체를 활용 소수를 효율적으로 구할 수 있다.

1. 소수 찾기

먼저 소수를 분별한다. ( max값을 찾아서 할 수 있지만 최대값 1,000,000인 점을 감안 미리 1,000,000까지 소수를 찾는다. )

    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

2. 골드 바흐 파티션 구성

1. 양쪽에서 숫자를 줄여가며 소수 체크를 한다. ( 이 때 양쪽에서 검사하기 때문에 절반만 사용한다. )

2. 둘 다 소수일 때 count를 증가시킨다.

3. count를 반환한다.

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }

미리 찾아둔 소수를 활용하고 반복문을 효율적으로 사용하면 비교적 쉬운 문제이다.
1,000,000 이하의 소수는 미리 생성해도 처리 가능하지만,
숫자가 매우 커질 경우에는 입력값의 최대값을 기준으로 소수를 구하는 것이 더 효율적이다.

이번 문제는 두 수의 합이 N이 되어야 하므로, 다음과 같은 방식이 적합하다.다만, 이전에 선택 정렬 문제에서 사용한 인덱스를 활용한 방식으로 데이터를 저장하는 방법도 고려할 수 있다.

전체 코드

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

public class Main {

    private static boolean[] isPrime;

    public static void main(String[] args) throws IOException {
        solve();
    }

    private static void solve() throws IOException {

        sieveOfEratosthenes(1000000);

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        for(int i = 0;i<N;i++){
            int num = Integer.parseInt(bufferedReader.readLine());
            String result = String.valueOf(findGBPartitions(num));
            stringBuilder.append(result)
                    .append("\n");
        }

        System.out.println(stringBuilder);
    }


    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }
}

maven, Spring, Junit 등 IntelliJ를 사용하면 편하다.
하지만 대부분 VS Code를 대부분 처음에 사용한다고 보는데
그 때 항상 써왔던 코드 정리를 찾아 보고 한다.

키보드를 하나만 더 추가해 4개만 누르면 된다
Ctrl + Alt + Shift + L
이후 다음과 같은 창이 뜬다

그럼 다음과 같이 정리된다.

코드 정리 전

코드 정리 후

개발시 가독성은 매우 중요한 요소 중 하나이다.
코드 작성시 정리는 기본적인 요소이므로 해야한다.