[Java] BOJ 13909: 창문 닫기와 힙 메모리 한도

---

요즘 변수명을 의미 있게 작성하려고 노력하는 중이다. 물론 알고리즘을 풀 때는 편의상 내가 알 수 있을 정도로만 작명한다. 동시에 메서드는 최대한 빼서 구현하는 편인데, 특별한 이유는 없고 메서드를 만드는 것에 익숙해지고 싶어서다.

---

창문 닫기 문제는 9단계에 위치했지만 앞선 단계들보다 쉽다. 그래서 크게 생각할 점 없이 코드를 짤 수 있었다.

---

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

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

public class Problem13909 {

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

        int[] windows = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                doWindow(windows, j);
            }
        }

        int count = 0;

        for (int i = 1; i <= N; i++) {
            if (windows[i] == 1) {
                count++;
            }
        }

        System.out.println(count);
    }

    static void doWindow(int[] windows, int i) {
        if (windows[i] == 0) {
            windows[i] = 1;
        } else if (windows[i] == 1) {
            windows[i] = 0;
        }
    }
}

---

테스트 입력도 몇 개 해보니 문제없이 돌아가는 듯했다. 단, 첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다. 이 문장이 마음에 걸렸는데, 처음에는 이것이 int와 long을 구분하라는 의미인가 싶었다. 근데 21억이라니, long도 아닌 걸 굳이 왜 강조해두었을까.

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Problem13909.main(Problem13909.java:13)

 

결과는 자바 힙 영역 초과다. 자바의 기본 힙 메모리 크기는 약 1GB에서 2GB 정도로 설정되어 있다. 이 크기 이상으로 배열을 만들었기에 OutOfMemoryError가 발생한 것이다.

 

항상 보면, 이런 문제의 정답은 의외로 코드 몇 줄 안 되는 경우가 많다. 그래서 조금 더 고민해보니 굳이 배열을 생성할 필요도 없는 문제라는 걸 알았다.

---

각 창문 입장에서 보았을 때, 창문은 약수의 개수만큼 열리고 닫힌다. 창문의 개수와 사람의 수가 같은 N이기 때문이다. 결국 열린 창문은 제곱수에 해당하는 창문이다. (1번 창문, 4번 창문, 9번 창문...)

---

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

public class Problem13909 {

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

        System.out.println((int) Math.sqrt(N));
    }
}

---

최종적으로 N의 제곱근을 구하고 정수 부분을 출력해 N 이하인 제곱근의 개수를 출력하였다.

---