[알고리즘] 자바 코드 실행 시간 단축 Tip (백준 2167)

백준 문제를 풀다가 코드 실행시간이 다른 정답자분들의 비해 커서 조금이라도 시간을 단축하는 방법이 있는지 찾아보다가 알게 된 정보에 대해서 공유하고자 합니다!

제 코드 체점 결과입니다.

다른 분들의 코드 체점 결과입니다.

보시면 굉장히 차이가 많이 나는 것을 확인할 수 있습니다. 상위 등수에 있는 분들의 코드를 보면 공통적으로 보이는 점이 있습니다.

 

1. Scanner이 아닌 BufferedReader 사용

---

Scanner의 경우 1KB 크기의 상대적으로 작은 버퍼를 갖기에 입력을 받는 즉시 전달되지만 BufferedReader의 경우는 8KB 크기의 버퍼를 가지고 있어 버퍼에 입력값들을 저장해 둔 뒤에 한 번에 전송하기 때문에 속도가 더 빠르다고 합니다! 그뿐만 아니라, Scanner는 입력 과정에서 내부에서 정규 표현식 적용, 입력값 분할, 파싱 과정 등을 거치기 때문에 속도가 느리다고 합니다. 아래는 2167번 문제를 Scanner을 사용하여 작성한 코드입니다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int NM_arr[][] = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				NM_arr[i][j] = sc.nextInt();
			}
		}
		
		int K = sc.nextInt();
		int K_arr[][] = new int[K][4];
		
		for(int i = 0; i < K; i++) {
			for(int j = 0; j < 4; j++) {
				K_arr[i][j] = sc.nextInt();
			}
		}
		
		for(int l = 0; l < K; l++) {
			int i = K_arr[l][0];
			int j = K_arr[l][1];
			int x = K_arr[l][2];
			int y = K_arr[l][3];
			int sum = 0;
			int tmp = j;
			
			for(; i <= x; i++) {
				for(; j <= y; j++)
					sum += NM_arr[i-1][j-1];
				j = tmp;
			}
			System.out.println(sum);
		}
	}
}

다음 코드는 BufferedReader와 BufferedWriter를 사용하여 작성한 코드입니다.

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

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));
		
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int NM_arr[][] = new int[N][M];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				NM_arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int K = Integer.parseInt(br.readLine());
		int K_arr[][] = new int[K][4];
		
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 4; j++) {
				K_arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int l = 0; l < K; l++) {
			int i = K_arr[l][0];
			int j = K_arr[l][1];
			int x = K_arr[l][2];
			int y = K_arr[l][3];
			int sum = 0;
			int tmp = j;
			
			for(; i <= x; i++) {
				for(; j <= y; j++)
					sum += NM_arr[i-1][j-1];
				j = tmp;
			}
			bw.write(String.valueOf(sum) + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
    }
}

BufferedReader와 BufferedWriter을 사용한 코드가 실행시간이 짧은 것을 확인할 수 있습니다!

 

2. StringBuffer 보다는 StringBuilder 사용

---

StringBuffer와 StringBuilder의 가장 큰 차이점은 동기화 여부입니다. StringBuilder는 동기화를 지원하지 않지만 StringBuffer는 동기화를 지원하기에 멀티 스레드 환경에서 안전하게 동작하지만 성능이 StringBuilder에 비해서 느립니다.

아래는 StringBuffer와 StringBuilder를 사용했을 시에 시간 차이입니다.

public class Main {
	public static void main(String[] args) throws IOException {
		long beforeTime = System.nanoTime();
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<1000000; i++) {
			sb.append("A");
		}
		long afterTime = System.nanoTime();
		long diffTime = (afterTime - beforeTime);
		System.out.println("코드 실행시간 : " + diffTime);
	}	
}

public class Main {
	public static void main(String[] args) throws IOException {
		long beforeTime = System.nanoTime();
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for(int i=0; i<1000000; i++) {
			bw.write("A");
		}
		long afterTime = System.nanoTime();
		long diffTime = (afterTime - beforeTime);
		System.out.println("코드 실행시간 : " + diffTime);
	}
}

출력하는 문자열의 크기가 작은 경우에는 큰 차이가 없겠지만, 위의 예시코드와 같이 문자열의 크기가 커질수록 성능면에서 차이가 많이 난다는 것을 확인할 수 있습니다!!

 

참고자료

---

 

2167번: 2차원 배열의 합

 

자바 String, StringBuilder 그리고 StringBuffer 성능 차이 비교