백준 13909 - Java

문제

 

내 풀이

풀이 1: boolean을 사용해서 true => false  / false => true로 변환하는 알고리즘을 생각하여 문제를 풀었으나 Memory Limit Exceeded 오류가 나왔다.  

 

64MB 메모리 제한을 고려할 때, 현재 코드에서 메모리 과잉 사용이 발생할 수 있는 주요 부분은 boolean [] isPrime = new boolean [n + 1]; 배열입니다. 이 배열의 크기는 입력값 n에 따라 결정되며, n이 클 경우(예: 2,100,000,000) 매우 큰 메모리를 필요로 하게 됩니다.

메모리 사용량 계산:

• Java에서 boolean 타입은 배열로 사용될 때 일반적으로 1비트를 사용한다고 알려져 있지만, 실제로는 최소 1바이트(8비트)를 사용합니다. 이는 Java의 메모리 정렬 및 관리 방식 때문입니다.
• 따라서, boolean 배열의 크기는 n이 2,100,000,000일 때 약 2.1GB (2,100,000,000 바이트)를 차지하게 됩니다. 이는 64MB 제한을 크게 초과합니다.

 

chatGPT를 사용하여 이유를 찾아본 결과 위와 같은 이유가 메모리 과잉 사용의 원인이 된 것이다. 

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

public class CloseWindow {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int count = 0;

        boolean[] isPrime = new boolean[n + 1]; // 창문 상태를 나타내는 배열, n+1 크기로 초기화

        //전체 1로 초기화 . 이때 1은 true로, 0은 false로 할 것임.
        for (int i = 1; i <= n; i++) {
            isPrime[i] = false;
        }

        //i * i번째 0 -> 1 / 1 -> 0 변경
        for (int i = 1; i * i <= n; i++) {
            isPrime[i * i] = !isPrime[i * i];
        }

        // 열려 있는 창문의 수를 계산
        for (int i = 1; i <= n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(1+ " ");
            }else{
                System.out.print(0+ " ");
            }
        }
        System.out.println();
        System.out.println(count);
    }
}

 

풀이 2 : 그래서 다른 방법을 생각해 보았고 , 굳이 배열을 만들어서 메모리 낭비를 할 것 없이 n번째를 계산해서 count만 증가해주면 되는 것이다.

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

public 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 count = 1;

        for(int i=2;i*i<=N;i++){
            count++;
        }
        System.out.println(count);

    }
}

 

Time Limit 뿐만 아니라 이제는 Memory Limit 까지 생각하여야 한다. 아무 생각 없이 문제를 풀지 말고 다시 한번 제한 조건들을 검토하는 습관을 들이는 것이 필요하다고 생각이 든다.

특히 이 문제는 보자마자 배열이 생각이 났고 다른 방법은 생각조차 안들었는데 아래 문제를 풀면서 결국 굳이 배열로 배열한 후 count++을 할 필요 없이 그냥 count만 ++ 했으면 되는 일이었다. 굳이 필요 없는 코드를 사용을 안 하도록 조금 더 문제에 대한 고민을 해야 할 것이다. 

풀이 1에서 boolean 아니여도 그냥 배열중에 integer로 하여도 된다. 왜냐하면 ==0 일 때와 ==1일 때로 나눠서 해도 된다. 다만 boolean이 먼저 생각이 났기에 이렇게 풀긴 하였다.  아마 이전 소수 문제들을 풀면서 boolean을 많이 써서 그런 것이다.  그렇다면 앞에 소수문제들도 다른 풀이들이 있지 않을까 라는 생각이 든다.