[알고리즘] 백준 15552 빠른 A+B - Java

백준 문제를 풀다가 보니 정말 인상 깊었던 알고리즘 문제가 있어서 글로 남기고자 한다.

바로 15552번의 빠른 A+B인데 시간제한이 있다는 점이 너무 재밌었다.

*시간제한은 Java기준 1.5초, 즉 1500ms 이내여야 한다.*

 

시작하기 전에 필자는 수업시간에 배운 BufferedReader을 사용해야겠다고 마음먹고 시작했다.

Scanner을 쓰면 시간초과가 된다.

먼저 이 둘의 차이를 알아보고자 한다.

---

Scanner과 BufferedReader의 차이점

Scanner의 동작 방식

1. Scanner는 내부적으로 정규표현식을 사용하여 입력을 파싱한다. 이 과정에서 추가적인 처리시간이 필요하다.
2. 데이터를 읽을 때마다 시스템 콜이 발생하여 매번 바이트 단위로 읽어온다.
3. 동기화 처리가 들어가 있어 멀티스레드 환경에서는 안전하지만, 단일 스레드 환경에서는 불필요한 오버헤드가 발생한다.

BufferedReader의 동작 방식

1. 내부적으로 8192 바이트 크기의 버퍼를 사용하는데, 이는 한 번에 많은 양의 데이터를 읽어올 수 있다는 의미가 될 수 있다.
2. 문자열 파싱 시 정규표현식을 사용하지 않아 처리 속도가 빠르다.
3. 버퍼 사용으로 인해 시스템 콜 횟수가 현저히 줄어든다.

실제 처리 속도 차이를 보자면

Scanner는 대략 1초당 10만건 처리를,

BufferedReader는 대략 1초당 100만건 처리를 한다고 알려져있다.

 

따라서 대용량 데이터 처리나 알고리즘 문제 해결 시에는 BufferedReader/BufferedWriter 조합을 사용하는 것이 훨씬 효율적이라고 보면 된다.

---

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            bw.write(Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken()) + "\n");
        }
        br.close();

        bw.flush();
        bw.close();
    }
}

 

전체 코드를 차근차근 살펴보자면,

먼저 필요한 클래스들을 import 했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.io.IOException;

 

입력 받는 부분은 BufferedReader을 사용하였고, readLine() 메소드를 통해 한 줄씩 읽어들일 수 있게 했다.

문제에서 정해준데로 첫 줄에는 테스트 케이스(N)의 개수를 입력받았다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());

 

그 다음에 StringTokenizer를 사용하여 공백으로 구분된 두 수를 분리했다.

각 줄마다 새로운 StringTokenizer 객체를 생성하고, BufferedWriter을 사용하여 결과를 출력했다.

1. write() 메소드로 출력할 내용을 버퍼에 담고
2. flush()를 호출하여 한 번에 출력하였다.
3. 마지막으로 사용한 자원들을 close() 메소드로 닫아준것을 볼 수 있다.

StringTokenizer st;
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine(), " ");
	bw.write(Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken()) + "\n");
}
    
br.close();
bw.flush();
bw.close();

 

이 외에도 더 빨리 덧셈을 처리할 수 있는 알고리즘이 있을 것이다.

필자는 이 외의 속도를 높일 수 있는 방법을 공부해나갈 예정이다!