Java Efficient Integer Read
Java Efficient Integer Read
Java에서 정수 입력받기
- Java 코딩 테스트 문제를 풀 때, 많은 수의 정수를 입력받아야 하는 경우가 존재
- 일반적으로는 BufferedReader로 줄 단위로 입력받은 후 StringTokenizer를 이용해 parsing
- 그러나 이 방법은 입력이 클 수록 매우 많은 메모리와 시간을 요구하게 됨
System.in.read() 활용
- Java의
System.in.read()메소드를 활용하면 ASCII 코드를 빠르게 입력받을 수 있음 - 이를 활용해 다음과 같은
read()함수는 매 번 정수를 읽어들여서 반환
private static int read() throws Exception {
int number = System.in.read() & 15;
int reader;
while ((reader = System.in.read()) > 32) {
number = (number << 3) + (number << 1) + (reader & 15);
}
return number;
}
코드 설명
- ASCII 코드를 정수로 변환하기
int number = System.in.read() & 15;
System.in.read()로 숫자의 ASCII 코드를 읽어 들임. 즉,'0'부터'9'사이의 ASCII값'0'의 ASCII 코드는 48이므로,'x'의 ASCII 코드는x + 48임- 즉,
System.in.read() - 48을 하면 입력한 숫자를 그대로 받을 수 있음 - 48은 이진수로
110000이고,'x'의 ASCII 코드는 48부터 57 사이의 값이므로, 이진수로는11abcd형태로 표현됨 - 이 때
11abcd에서110000를 빼면abcd이고, 이는11abcd & 001111와 같음 001111은 15이므로,System.in.read() - 48과System.in.read() & 15는 동치
- 여러 자리 수를 입력 받기
int reader;
while ((reader = System.in.read()) > 32) {
number = (number << 3) + (number << 1) + (reader & 15);
}
return number;
reader라는 변수에 현재 입력받은 ASCII 코드를 저장number는 반환할 정수 값- 현재 입력값이
space(ASCII code: 32) 혹은newline(ASCII code: 10)일 경우- 입력을 다 받은 것이므로 반복문을 탈출하고
number를 반환
- 입력을 다 받은 것이므로 반복문을 탈출하고
- 현재 입력받은 값이
'0'~'9'인 경우- 지금까지 입력받은 값 뒤에 추가적인 숫자가 있다는 뜻이므로, 반복문을 수행
number를지금까지 입력받은 값(number) * 10 + 현재 입력받은 값으로 변경해야 함number * 10은(number << 3) + (number << 1)와 동일- 현재 입력받은 값은
(reader & 15)임
- 주의점
- 이 read 함수는 숫자와 숫자사이에 정확히 한 개의 공백 혹은 newline만 있다고 가정한 경우 성립
- 입력받는 방식에 따라 함수를 수정할 필요가 존재
- CRLF를 사용하는 경우에는,
\r에 대한 별도의 처리 필요 - 음수를 입력받아야 하는 경우에는
-에 대한 추가적인 코드가 필요
실제 시간 / 메모리 비교
백준 10942 문제를 입력받는 방식만 다르게 해서 두 가지 방법으로 풀어 봄. 약 100만줄의 입력을 받는 문제
- BufferedReader + StringTokenizer를 통해 입력받기
StringTokenizer st;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
//logic
}
- read 함수 이용
for (int i = 0; i < M; i++) {
start = read();
end = read();
//logic
}
- 결과
- 아래가 1번, 위가 2번 결과
- 시간도 꽤 차이나지만 메모리에서도 크게 차이남을 확인 가능
