안녕하세요! 자바로 백준이나 SWEA 같은 알고리즘 문제를 풀다 보면, 한 번쯤은 이런 억울하고 답답한 경험을 해보셨을 겁니다.
"분명히 시간 복잡도는 $O(N)$으로 완벽하게 맞췄고 알고리즘 로직도 흠잡을 데가 없는데, 왜 데이터 개수가 커지면 '시간 초과(TLE)'가 뜨면서 프로그램이 픽픽 쓰러질까?"
"코드를 C++나 파이썬으로 똑같이 옮겨 적으면 통과하는데, 왜 자바만 오답 처리가 되는 거지..?"
지난 1편에서는 Scanner의 버퍼 대참사와 nextLine()의 함정을 다뤘었는데요.
이번 2편에서는 자바 입출력의 양대 산맥인 Scanner와 BufferedReader가 내부적으로 어떻게 다르게 동작하는지, CS 지식과 공식 문서를 참고해서 탐구해보겠습니다.
1. Scanner와 BufferedReader의 근본적 차이 (I/O 모델)
가장 먼저 이 두 클래스가 입력을 받아들이고 가공하는 근본적인 방식의 차이(I/O 모델)를 알아야 합니다.
Scanner의 '정규식(Regex) 기반 파싱' 오버헤드
자바의 java.util.Scanner는 입력을 단순히 읽는 것에 그치지 않고, 사용자가 원하는 타입(int, double, String 등)으로 즉시 변환해 주는 똑똑한 클래스입니다.
하지만 이 편리함 뒤에는 어마어마한 CPU 사이클 낭비가 숨겨져 있습니다.
Scanner는 들어오는 모든 데이터를 파싱할 때 내부적으로 정규식(Regular Expression) 패턴 매칭을 수행합니다.
예를 들어, sc.nextInt()를 호출하면 다음과 같은 일이 일어납니다.
- 입력 스트림에서 구분자(공백, 줄바꿈 등)를 기준으로 토큰을 잘라냅니다.
- 잘라낸 토큰이 숫자의 형태(정규식 패턴)를 만족하는지 검사합니다.
- 만족한다면 그제야 숫자로 형변환하여 반환합니다.
이 과정에서 매번 정규식 검사를 돌려야 하므로 CPU 레벨에서는 수많은 분기 예측과 연산이 일어나게 되고, 이는 고스란히 처리 시간의 지연(오버헤드)으로 이어지게 됩니다.
즉, 데이터를 읽는 물리적 속도보다 가공(Parsing)하는 데 쓰는 CPU 연산 비용이 더 비싼 주객전도 상황이 벌어지는 거죠.
BufferedReader의 'Buffered I/O'와 시스템 콜(System Call) 절약
반면 java.io.BufferedReader는 이름 그대로 입력받은 데이터를 메모리 버퍼에 꾹꾹 눌러 담아두고 한 번에 처리하는 단순한 방식을 씁니다.
여기에 핵심 CS 개념인 시스템 콜이 등장합니다.
프로그램이 하드웨어(키보드, 디스크 등)로부터 데이터를 직접 읽어올 수 없기 때문에, 운영체제(OS) 커널에 "대신 데이터를 읽어달라"고 요청해야 하는데 이를 시스템 콜이라고 합니다.
자바에서 System.in.read()를 호출할 때마다 JVM은 OS 커널에 시스템 콜을 보내게 되는데요. (물론 하드웨어 직접적인 권한이 없으므로 OS 커널에게 시스템 콜 통해서 작업을 요청하는 것입니다)
[User Space (JVM)] -- (System Call) --> [Kernel Space (OS)] --> [Hardware (Disk/Keyboard)]
* 이 과정에서 모드 전환 및 컨텍스트 스위칭이 발생하여 CPU 자원을 대량으로 소모함!
이 시스템 콜이 일어날 때마다 CPU는 하던 일을 멈추고 유저 모드에서 커널 모드로 전환해야 합니다.
이때 CPU가 현재 실행 중이던 유저 프로그램의 상태(PC 값, 레지스터 상태 등)를 전부 안전한 메모리에 대피(레지스터 백업)시켰다가 돌아와서 복구해야 하므로 꽤 상당한 비용이 듭니다.
마치 마트에서 사탕 한 개를 살 때마다 매번 옷을 챙겨 입고 문밖으로 나가는 번거로운 심부름과 같습니다. ㅎㅎ
Scanner는 내부 버퍼가 작고 토큰 단위로 자주 끊어 읽기 때문에 이 무거운 시스템 콜(심부름)을 수없이 많이 날리게 되는 것이죠.
반면, BufferedReader는 기본적으로 아주 커다란 버퍼(8,192 chars)를 가지고 있습니다.
이 8192자라는 크기가 감이 잘 안 오실 수 있는데요.. 한글은 자바 내부에서 한 글자당 2바이트(UTF-16)를 차지하므로, 실제 버퍼의 바이트 크기는 16KB 수준입니다.
글자 수와 공백을 모두 포함하여 한글 기준으로 대략 8,192글자를 한 번에 담을 수 있는 사이즈입니다.
처음 데이터가 들어올 때 시스템 콜을 딱 한 번만 날려서 이 버퍼를 가득 채워두고, 그 이후의 읽기 작업(read(), readLine())은 OS 커널을 다시 부를 필요 없이 메모리 영역(User Space)에 이미 적재된 버퍼에서 쏙쏙 빼오기만 합니다.
(버퍼가 비어있을 때만 시스템 콜 호출해서 버퍼를 다시 채워버립니다)
최악의 경우에도 시스템 콜 호출 횟수가 수십, 수백 배 줄어드니 속도가 많이 빠를 수밖에 없는 구조인 것입니다.
2. 성능 격차의 CS적 이유 (데이터 접근과 메모리 복사)
메모리와 가비지 컬렉터(Garbage Collector)의 관점에서도 두 클래스의 격차는 많이 벌어집니다.
graph TD
subgraph Scanner Mode
A[Input Stream] --> B(Regex Delimiter)
B --> C[Create Matcher Obj]
B --> D[Create String Obj]
C & D --> E((Heavy GC Pressure))
end
subgraph BufferedReader + StringTokenizer Mode
F[Input Stream] --> G[8KB Buffer]
G --> H(StringTokenizer)
H --> I[Original String Pointer Index]
I --> J((Minimal Object Creation))
endScanner가 유발하는 GC 폭탄
Scanner로 입력을 토큰으로 잘라내며 파싱을 할 때, 내부 정규식 클래스는 매 단계마다 Pattern 인스턴스 검사 및 Matcher 객체를 비롯한 수많은 임시 객체들을 힙 메모리에 생성해 냅니다.
만약 입력 데이터가 100만 개(10^6)가 넘어간다면 어떻게 될까요?
순식간에 힙 영역에 단명 객체(Short-lived objects)들이 수백만 개가 쌓이게 됩니다.
여기서 단명 객체란 '생성되자마자 아주 잠깐 쓰이고 곧바로 쓸모없어져서 가비지가 되는 수명이 아주 짧은 객체'들을 말하는데요. 정규식 패턴을 비교하거나 문자열 토큰을 쪼갤 때 연산용으로 잠깐 거쳐 가며 생성되는 임시 객체들이 여기에 해당합니다.
자바의 JVM은 메모리가 부족해지면 이 쓰레기들을 청소하기 위해 GC를 가동합니다.
이때 GC의 가장 고전적이면서도 근본적인 알고리즘인 'Mark and Sweep (사용 중인 객체는 식별(Mark)하고, 남은 가비지는 쓸어버리는(Sweep) 방식)'이 수행됩니다.
살아있는 객체를 정확히 골라내고 메모리 상태를 고정한 채 안전하게 청소하려면, 객체들의 연결 주소가 변하지 않아야 하므로 JVM은 작동 중인 애플리케이션의 모든 쓰레드를 일시적으로 전부 멈춰 세우게 됩니다.
이것을 바로 Stop-The-World (STW) 현상이라고 부릅니다..
이거는 Mark and Sweep개념과도 연결되됩니다.
Mark and Sweep 관련해선 Swift라는 언어에서, 관리하는 ARC와의 차이를 간단하게 알아봤었는데~ 기억이 나네요.[Swift ARC vs GC 글 바로가기]
결국 알고리즘 코드가 100만 번 돌며 열심히 계산하는 도중에, GC가 수시로
"잠깐 동작 멈춰봐, 메모리 청소하게!"
하고 훼방을 놓으며 프로그램을 수십 번씩 정지시키니 실행 시간이 늘어날 수밖에 없는 것이더라구요.
BufferedReader + StringTokenizer의 찰떡궁합
반면 많은 자바 알고리즘 고수들이 즐겨 쓰는 BufferedReader와 StringTokenizer 조합은 메모리를 대단히 아낍니다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
BufferedReader.readLine()은 한 줄을 통째로 긁어와 문자열 객체 단 하나만 만듭니다.
그리고 StringTokenizer는 이 문자열을 토큰 단위로 나눌 때, 복잡한 임시 가비지 객체를 마구 쏟아내지 않습니다.
내부적으로 원본 문자열을 가리키는 인덱스 포인터(Pointer/Index) 정보만 유지하며 훑어 나가기 때문인데요.
객체 생성이 적은데 왜 GC가 안 끼어들까?
자바 힙(Heap) 메모리에서 새로운 객체가 생성되면 우선 Eden 영역이라는 곳에 들어갑니다.
데이터가 100만 개일 때 Scanner나 split()은 매 루프마다 새로운 가비지 객체 수백만 개를 Eden 영역에 초고속으로 때려 넣습니다.
그러다 보니 Eden 영역이 순식간에 포화 상태가 되어 JVM은 어쩔 수 없이 쓰레기를 치우기 위해 Minor GC를 연쇄적으로 발동하게 되고, 이 과정에서 수많은 STW(멈춤)가 누적되어 시간 초과가 나게 되는 것이죠.
반면, StringTokenizer는 원본 문자열을 복사하거나 배열 객체를 무분별하게 양산하지 않고 단순히 포인터 위치 정보만 갱신하며 연산하기 때문에 힙 메모리(Eden 영역)를 거의 더럽히지 않습니다.
버퍼가 꽉 차서 GC를 긴급 호출할 조건 자체가 성립하지 않으니, 프로그램이 방해 없이 처음부터 끝까지 쌩쌩 달릴 수 있는 비결이 바로 여기 있습니다!
3. 공식 문서 기반의 정확성 분석 (물리적 버퍼 크기)
우리가 쓰는 도구의 스펙을 파악하는 데는 역시 공식 문서만 한 게 없더라구요.
Oracle의 자바 공식 문서를 살펴보면 BufferedReader를 다음과 같이 정의하고 있습니다.
BufferedReader 공식 문서 정의 [ 링크 바로가기 ]
"Reads text from a character-input stream, buffering characters so as to provide for the efficient reading of characters, arrays, and lines."
여기서 핵심 단어는 역시 efficient(효율적인)인데요.
물리적으로 이 효율성을 증명하는 것이 바로 두 클래스의 기본 버퍼 크기(Default Buffer Size) 차이입니다.
- Scanner의 기본 버퍼 크기:
1,024 chars(1KB) - BufferedReader의 기본 버퍼 크기:
8,192 chars(8KB)
char타입은 자바에서 2바이트를 차지하므로, BufferedReader는 메모리에 상시 약 16KB의 완충 지대를 올려두고 입력을 받아들이는 셈입니다.
입력 파일의 크기가 클수록, 디스크에서 버퍼로 데이터를 끌어오는 단위가 8배나 크기 때문에 실제 물리적인 하드웨어 I/O 병목을 메모리 영역에서 유연하게 흡수해 줍니다.
이 8배의 버퍼 체급 차이가 알고리즘 테스트 케이스 통과 여부를 결정짓는 든든한 방패막이가 되어 주더라구요.
4. 알고리즘 문제에서의 TLE 발생 원리
마지막으로 10^6 (100만) 개 이상의 대량 입력 데이터가 주어졌을 때 두 방식의 누적 성능 격차를 체계적으로 정리해 보겠습니다.
컴퓨터 아키텍처 관점에서 입출력에 드는 비용은 다음과 같이 요약할 수 있습니다.
| 구분 | Hardware Access (I/O) | Parsing Cost (CPU Regex) | Memory Allocation (GC) |
|---|---|---|---|
| Scanner | 아주 비쌈 (1KB 단위 잦은 디스크 접근/System Call) | 극도로 높음 (정규식 엔진 매칭 연산) | 지옥 수준 (Matcher 및 임시 객체 매번 생성) |
| BufferedReader + ST | 매우 저렴 (8KB 단위 일괄 버퍼 적재/System Call 최소화) | 없음 (단순 Pointer 인덱싱 탐색) | 매우 가벼움 (원본 한 줄 객체 및 포인터 정보만 유지) |
100만 개의 정수 입력을 받을 때, Scanner는 비싼 시스템 콜을 쉴 새 없이 날리면서 CPU로 무거운 정규식 파싱을 돌리고, 힙 메모리를 가비지 객체로 꽉 채워 GC를 강제로 실행시킵니다.
반면 BufferedReader + StringTokenizer 조합은 단 몇 번의 시스템 콜로 버퍼에 얹은 뒤, 단순 인덱스 탐색으로 데이터를 가공하므로 하드웨어 접근 비용과 CPU 연산 비용 모두를 혁신적으로 아끼게 됩니다.
결국 이 작은 입출력 메서드의 선택 하나가 0.1초와 2.5초의 엄청난 실행 시간 차이를 만들게 되고, 무자비한 TLE 대참사를 결정짓는 원인이 됩니다.
결론
- 데이터를 읽을 때 Scanner는 정규식을 타는 느린 파서이고, BufferedReader는 버퍼에 가득 채워 한 번에 빠르게 전송하는 고속 수송 트럭!!
- 대용량 데이터(10^5 ~ 10^6 이상)를 다룰 때는 OS 시스템 콜 횟수를 낮추고 GC의 오버헤드를 막기 위해
BufferedReader와StringTokenizer조합을 사용하면 좋겠네요.
시간이 난다면 다음 3편에서는 BufferedWriter와 StringBuilder가 버퍼를 비워내는 원리를 탐구하려구 합니다.
감사합니다.
