문제를 풀다가 더 최적화된 방법이 있나 찾아보다 1등의 코드와 비교하게 되었다.
응??
1등과 코드의 내용은 거의 비슷하지만 시간 속도 차이는 무려 2배..
차이점을 찾아보니 1등 코드는 아스키코드+비트연산으로 read() 함수를 구현했고, 나는 BufferedReader를 사용했다.
(위 이미지는 본인의 동일 코드에서 read()를 사용할 때와, br를 사용할 때의 시간 차이이다.)
종종 문제들의 상위권 코드를 보면 read()가 있는 것을 봤는데, 해당 read() 메소드를 따로 구현해야하고 외우기도 힘들어 BufferedReader를 써왔는데 이렇게 속도 차이가 날 줄은 몰랐다.
문제에서 입력받는 부분이 비중이 클수록 차이가 커진다.
때문에 해당 read() 메소드를 분석하고자 한다.
아스키코드표
System.in.read()
일단 이 read()함수 구현을 위한 기반이 되는 메소드이다.
문자 하나를 입력받아 아스키코드값을 출력한다.
import java.io.*를 하면 사용할 수 있다.
문제에 따라 문자 하나를 입력받고 싶으면 (char)로 형변환을 해주면 된다. 하지만 문자열이나 문자를 다루는 알고리즘 문제에서는 귀찮으니 그냥 BufferedReader를 쓰자.
read() 메소드 분석
read()메소드는 문자가 없는 0을 포함한 자연수의 입력값을 받는 알고리즘 문제에서 보통 사용된다. 그리고 해당 유형의 문제에서는 숫자와 공백으로 입력을 받는다.
1) char형 계산
char형 계산으로 숫자(n)을 입력받고 뒤의 입력값이 숫자이면 n에 계산, 문자(공백 등)이면 숫자 계산을 끝낸다. 또한, 윈도우에서는 줄바꿈 계산을 따로 해줘야한다. (백준 문제 제출 환경에서는 필요없음)
static int read() throws Exception {
int c;
int n = System.in.read() - '0';
c = System.in.read();
while (c > ' ') {
n = 10 * n + c - '0';
c = System.in.read();
}
if (c == '\r') {
System.in.read(); // '\n'. For CRLF(Windows)
}
return n;
}2) 아스키 코드값 사용 및 정리
아스키 코드값을 사용하고 코드를 깔끔하게 정리하면 아래와 같이 된다.
static int read() throws Exception {
int c, n = System.in.read() - 48;
while ((c = System.in.read()) > 32)
n = 10 * n + c - 48;
if (c == 13) System.in.read();
return n;
}3) 시프트 연산과 비트 연산 사용
먼저 System.in.read() & 15를 보자.
숫자의 아스키코드값은 48~57이다. 이 아스키코드값으로 숫자를 얻으려면 0의 아스키코드 48를 빼면 된다. (0~9)
즉, 이진수로 110000~111111에서 110000을 제외한 0000~1111값만을 확인하면 된다. 이를 &15 연산으로 계산한다.
그리고 n = (n << 3) + (n << 1) + (c & 15)는 n의 10배(8배+2배) + 새로운 숫자(c&15)로 n = 10 * n + c - 48 연산과 동일하다고 볼 수 있다.
static int read() throws Exception {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
if (c == 13) System.in.read();
return n;
}4) 정수 입력받기 (기존 read()에서 음수 포함)
지금까지의 코드를 이해했다면 음수를 포함하여 입력받는 것은 쉽다.
음수를 나타내는 -는 아스키코드값이 45이고 이를 따로 처리해주면 된다.
isNegative ? ~n + 1 : n 이 부분은 2의 보수를 이용하여 계산하는 것이다.
private static int read() throws Exception {
int c, n = System.in.read() & 15;
boolean isNegative = n == 13;
if (isNegative) n = System.in.read() & 15;
while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
return isNegative ? ~n + 1 : n;
}마치며
최적화 끝판왕이나 백준 순위를 올리고 싶은 욕망(?)이 있다면 쓰도록 하자.
다른 코테에서는 굳이...?라는 느낌이 든다. 이유는 따로 메소드를 구현해야 하며 알고리즘을 잘 짰다면 제한 시간 내에는 통과될 것이기 때문이다.
+ 사용 후기 (2023.02.16)
최근에는 read() 함수가 익숙해져 백준 문제를 풀 때, 매번 사용한다.
놀랍게도 알고리즘을 잘 짰다면 10문제 중 8문제는 TOP3 안에 든다.
은근히 순위권 안에 들어가는 성취감도 있고, 다른 사람이 내 코드를 참고했다는 알람을 받으면서 뿌듯함도 느낀다.
마치며에 쓴 것과 다르게 자주 사용할 것 같다..ㅎ
Reference
