[백준] 15552번 : 빠른 A+B - JAVA [자바]

 

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

15552번: 빠른 A+B

 

 

---

• 문제

 

※ 주의할 점

 

1. 시간제한은 1.5초다. 즉 1500ms 이내여야 한다. (위 이미지 하단 시간 제한 안내에 기재되어있음)
2. Scanner 사용하면 시간초과된다. 스캐너는 너무 느리다. 이유는 아래에서 설명하겠다.
3. System.out.printn 도 사용하면 시간초과된다. 

 

 

 

---

• 2가지 풀이 방법을 제시한다.

입력은 한 가지 방법으로 (BufferedReader) 사용하며 출력을 다르게 사용할 것이다.

 

이전 포스팅에서 출력에 따라 시간소요도 달라진다고 자주 언급했었는데 이제서야 제대로 비교할 수 있는 문제가 나왔다.

 StringBuilder, BufferedWriter 의 방식을 쓸 것이다.

 

필자가 제출했던 코드도 추가로 보여주려 한다. ( 참고로 어쩌다보니 JAVA 제출자 중 무려 5위에 랭크되었다! )

 

 

 

---

• System.out.println()을 사용하면 안풀리는 이유

우리는 모든 테스트케이스가 1.5초 즉, 1500ms 내의 시간에서 풀려야 한다.

 

문제에서 보면 최대 100만개의 테스트 케이스가 주어진다. 케이스가 늘어나면 늘어날 수록 문제점이 생기는데 바로 System.out.println()의 호출횟수 또한 증가한다는 것이다.

그래서 아무리 BufferedReader 을 써줬어도 System.out.println() 을 각 테스트 케이스마다 해주면 시간초과가 되어버린다.

[ 테스트 코드 및 결과 ]

<코드>

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
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());

		StringTokenizer st;
        
		for (int j = 0; j < N; j++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			System.out.println(a+b);
		}
	}
}

 

 

 

<결과>

 

보다시피 이렇게 시간 초과라고 딱 뜬다....

 

 

 

 

즉 각 테스트케이스마다 System.out.println() 을 호출해주게 되면 당연히 시간 또한 지연될 수 밖에 없기에 우리가 선택할 수 있는 방법은 크게 두 가지가 있다.

 

1.  StringBuilder 로 하나의 문자열로 계속 연결시킨 뒤 가장 마지막에 연결된 하나의 문자열을 출력시키는 방법.
2. BufferedWriter 로 버퍼에 담아둬았다가 한 번에 데이터를 보내는 방법

이렇게 있다.

 

BufferedReader 와 저 두 방법 중 어느 것을 같이 사용하더라도 문제는 풀 수 있다.

 

 

---

• Scanner를 사용하면 안풀리는 이유

 

(만약 입력에 대해 자세히 알고싶으면 아래 링크의 포스팅을 참고하면 된다.)

https://st-lab.tistory.com/41

JAVA [자바] - 입력 뜯어보기 [Scanner, InputStream, BufferedReader]

 

 

기본적으로 자바의 경우 Scanner를 사용해서는 풀 수 없다.

Scanner 자체가 regular expression, 즉 정규식을 남발(?)하기 때문이다.

물론 사용자 입장에서 편리한 점은 있겠지만 알고리즘에서는 사용자가 집적 필요에 따라 파싱(parsing)하는게 더욱 빠르기 때문에 BufferedReader을 쓰게 되는 것이다.

 

Scanner 자체가 입력을 받으면 구문분석을 위해 정규식을 거치게 되고 BufferedReader은 그런 특별한 구문분석이 없어서 속도차이가 발생 할 수 밖에 없다.

 

우리가 흔히 쓰는 Scanner.nextInt() 만 보더라도 다음과 같은 정규식에 맞는지를 분석한다.

 

실제로 내부적으로 이렇게 구성되어 있다.

 

(필자의 이클립스 util 패키지에 있는 Scanner.nextInt() 호출시 검사하게 되는 buildIntegerPatternString() 이다.

 

 

위의 로직을 대강 뜯어서 보자면 아래와 같다.

"("+ "([-+]?(" + "(("((?i)
["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"++)|"+
"("+"[\\p{javaDigit}&&[^0]]"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+"?"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+"?("+ "\\,"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+")+)"+")" + "))" + ")|(" +
 
 
"" + "(("((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"++)|"+
"("+"[\\p{javaDigit}&&[^0]]"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+"?"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|\\p{javaDigit})"+
"?("+"\\,"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+")+)"+")" + "" + ")|(" +
 
 
"\\-" + "(("((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"++)|"+
"("+"[\\p{javaDigit}&&[^0]]"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+"?"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+"?("+"\\,"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+
"((?i)["+"0123456789abcdefghijklmnopqrstuvwxyz".substring(0,radix)+"]|
\\p{javaDigit})"+")+)"+")" + "" + ")"

(이거 쓰느라 힘 좀 들었다...)

 

이 걸 모두 검사하고 return 하기 때문에 사실상 시간이 많이 소요될 수 밖에 없다.

그에 반해 BufferedReader은 위와같이 길고 많이 검사하지 않는다.

 

BufferedReader 도 뜯어서 보여드리고 싶지만 왔다갔다 해야할 게 많아서 너무 글이 방대해질 것 같으니 이 건 pass..

다만 궁금하다면 직접 BufferedReader 객체를 생성하고 BufferedReader.readLine(); 한다음 이 기점을 디버깅해서 함수를 끝까지 들여다 보면 된다. (F5키로 스텝을 넘어가면 된다.)

 

 

 

 

---

• 풀이

 

- 방법 1  [ 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));


		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();

	}
}

 

대중 적인 방법 중 하나다.

 

모든 입력은 BufferedReader.readLine() 으로 받았다.

 

테스트 케이스에서 주어지는 두 정수는 문자열 분리를 위해 매 반복마다 StringTokenizer 을 생성과 동시에 문자를 입력받는다.

( st = new StringTokenizer(br.readLine(), " ");

 

또한 다음 열에서 각 StringTokenizer 의 토큰 (분리되어있는 문자)을 반환하며,

반환되는 타입은 String 이므로 Integer.parseInt를 통해 int형으로 바꾸어 준다. 이렇게 바꾼 두 토큰을 더해준 값을 BufferedWriter.write() 에 넣어준다.

( bw.write((Integer.parseInt(st.nextToken())+Integer.parseInt(st.nextToken()))+ "\n"); )

 

그리고 거의 필수적으로 버퍼를 비운 뒤(flush) 닫아줘야한다(close).

 

위와같이 쓰면 아마 800ms 대의 시간이 나올 것이다.

 

 

 

 

 

---

 

- 방법 2 [ StringBuilder 사용 ]

 

 

StringBuilder 를 쓰는 방식이다. 알고리즘 자체는 위 방법 1 과 동일하다.

다만 BufferedWriter 대신 StringBuilder 로 대체할 뿐이다.

 

(데이터 양을 보았을 때 StringBuilder 가 더 빠를 수도 있다.)

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

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());
        
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
        
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			sb.append(Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken())).append('\n');
		}
		br.close();

		System.out.println(sb);

	}
}

 

 

 

필자가 쓰면서 테스트 해보니까 대략 600~700ms 정도를 왔다갔다 한다.

 

아무래도 100만개 정도까지는 StringBuilder 가 근소하게 더 빠르긴 한 것 같다.

(물론 데이터 양이 커지면 커질 수록 BufferedWriter 가 더 빠르다.)

 

 

 

---

• 필자의 코드
  

보편적인 방법까지는 아닌데 이 문제를 풀고보니 필자와 비슷하게 푼 사람들이 매우 많았다는 것을 보고 어느정도 알고리즘들이 정형화되어있구나 싶었다.

 

 

StringTokenizer 가 속도가 빠르긴 하나 매 반복문마다 생성해주고 함수를 호출해주는 것이 ( 그 것도 한 번씩만 분리하기 위해) 시간이 지연되는 원인 중 하나 일 수 있다. 그래서 이 시간도 줄이기 위해 고안한 방법이 String.substring() 메소드다.

우리는 문자열 분리 규칙이 매우 단순하다는 것을 알 수 있다. 그것은 바로 " " (공백) 을 기준으로 분리되니 이 위치만 알면 간단하면서도 빠르게 분리할 수 있을 것이라는 점이다.

또한 StringTokenizer 을 생성하지 않으니 메모리 또한 많이 줄어들 수 있다.

 

그럼 힌트 코드를 보여주겠다.

 

 

 

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

public class Main {

	public static void main(String[] args) throws Exception {

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

		for (int i = 0; i < N; i++) {		
			String str = br.readLine();
			int target = str.indexOf(" ");
			int result = Integer.parseInt(str.substring(0,target)) + Integer.parseInt(str.substring(target + 1));		
			sb.append(result+"\n");
		}
		
		br.close();
		System.out.print(sb);
    }
}

 

 

이 코드가 힌트다. 물론 이대로 제출해도 매우 상위권에 위치할 수 있다.

 

여러분들이 시간단축을 더 하고 싶다면 여기서 시간을 더 줄일 수 있는 방법을 고안하여 수정하고 올리면 되겠다.

 

 

 

 

그리고 무려 200ms 대를 기록하신 분이 계신데 코드를 보니까 입력 자체를 재정의해서 구현하셨다... 감탄밖에 안나왔다.. 필자도 시간이 되는대로 한 번 구현해놓아보아야 겠다..

 

 

 

---

• 성능 차이

 

위에서 부터 순서대로

 

채점 번호 : 17738216  -  필자 힌트 코드

채점 번호 : 17738210  -  BufferedReader + StringBuilder()  

채점 번호 : 17738187  -  BufferedReader + BufferedWriter  

 

보면 어떻게 알고리즘을 구현하느냐, 어떻게 출력을 받느냐에 따라 성능이 차이가 난다.

자바 성공률이 30%대 인데 아무래도 그냥 평소처럼 Scanner 를 썼거나 BufferedReader 을 썼어도 출력에서 시간초과 된 사람들이 많아서 그런 것 같다.

 

 

 

---

• 정리

 

이번 계기로 BufferedReader, StringBuilder, BufferedWriter 에 대해 어느정도 필요성을 느끼셨을거라 생각한다.

 

특히 Scanner 는 아마 자바를 배우고 있는 분들 대부분이 사용할 것이다.

더군다나 대학교 강의에서 대부분 BufferedReader 에 대해 파일입출력 part 때나 나오고 그 외에는 Scanner 로 모조리 입력받다보니 대부분 Scanner 에 익숙하기도 하고 필자가 아는 선에서는 성능 비교에 대한 언급이 많이 없기도 하다.

 

그러니 앞으로의 알고리즘 문제에서도 별다른 문제가 없다면 Scanner 보단 BufferedReader 을 사용하셨으면 한다.

또한 테스트 케이스가 많으면 StringBuilder 나 BufferedWriter 만 사용해주어도 시간은 엄청나게 단축되니 꼭 알아두셨으면 한다.