Fast I/O(정수 혹은 정수 배열)

알고리즘/기타

Fast I/O(정수 혹은 정수 배열)

mozzi329 2022. 8. 20. 21:24

728x90

📌 Fast I/O

알고리즘 문제를 풀다 보면 외적으로 최적화가 필요한 경우가 종종 생긴다. 그래서 빠른 입출력에 대해 고민해야할 필요가 종종 있다.

✔️ Scanner() 의 문제점

Scanner가 느린 가장 큰 이유는 정규 표현식의 남용이다.

Scanner.nextInt()는 내부적으로 아래와 같은 정규 표현식을 만족하는 입력을 찾으려 한다.

(([-+]?(((((?i)[0123456789]|\p{javaDigit})++)|([\p{javaDigit}&&[^0]]((?i)[0123456789]|\p{javaDigit})?((?i)[0123456789]|\p{javaDigit})?(\,((?i)[0123456789]|\p{javaDigit})((?i)[0123456789]|\p{javaDigit})((?i)[0123456789]|\p{javaDigit}))+)))))|(((((?i)[0123456789]|\p{javaDigit})++)|([\p{javaDigit}&&[^0]]((?i)[0123456789]|\p{javaDigit})?((?i)[0123456789]|\p{javaDigit})?(\,((?i)[0123456789]|\p{javaDigit})((?i)[0123456789]|\p{javaDigit})((?i)[0123456789]|\p{javaDigit}))+)))|(\-((((?i)[0123456789]|\p{javaDigit})++)|([\p{javaDigit}&&[^0]]((?i)[0123456789]|\p{javaDigit})?((?i)[0123456789]|\p{javaDigit})?(\,((?i)[0123456789]|\p{javaDigit})((?i)[0123456789]|\p{javaDigit})((?i)[0123456789]|\p{javaDigit}))+)))

Scanner가 이런 짓(?)을 벌이는 이유는 입력에 i18n/l10n 개념을 적용하려고 하기 때문이다.

※ i18n이란 internationalization(국제화)을 줄여서 i18n(i와 n 사이에 18글자가 있다는 뜻)
※ l10n이란 localization(현지화)을 줄여서 l10n(l과 n 사이에 10글자가 있다는 뜻)

자세한 내용 i18n과 l10n에 대해서 글 참조

예를 들어 Scanner.nextInt()는 "1,234,567"나 "1_234_567"과 같은 입력 또한 1234567로 인정한다. 안타깝게도 이러한 기능은 거의 모든 알고리즘 문제에서는 별 쓸모가 없고, 속도 저하의 원인으로만 작용한다.

결국,

문자 하나씩 받는게 제일 효율적이다 !

그래서 대부분의 알고리즘 문제가 정수 배열을 주어주고 12 7 4 8 9 10 -5 7 이런 식으로 공백을 구분해서 배열을 받으므로 정수나 정수 배열을 좀 더 효율적으로 받을 수 있는 방법을 소개하고자 한다.

✔️ System.in.read()

입력된 데이터를 한 바이트(아스키 코드)씩 읽어오는 메서드이다.

System.in.read()를 사용하면 입력되는 문자를 한 문자씩(아스키 코드 값) 가져올 수 있다.

이걸 활용해서 FastI/O(정수) 메서드를 구현해보자.

import java.io.IOException;

public class FastIO {
    private static int readInt() throws IOException {
        boolean isNegative = false; // 음수니?
        int totalPlusValue = 0;
        while (true) {
            // 입력 문자의 ASCII코드 값.
            // 가령 '0'이 들어왔으면 숫자 0이 아니라 '0'의 ASCII 코드값인 48이다.
            int inputChar = System.in.read();
            if (inputChar == ' ' || inputChar == '\n') { // 개행문자거나 공백이면 연산을 끊음
                return (isNegative)
                        ? -1 * totalPlusValue // 음수면 - 붙여서 반환
                        : totalPlusValue; // 양수면 그냥 반환
            } else if (inputChar == '-') { // 문자를 읽었는데 -가 붙어있으면 이 값은 음수임
                isNegative = true;
            } else {
                totalPlusValue = totalPlusValue * 10 + (inputChar - 48); // 기존 값을 10배하고 입력된 추가값을 파싱하여 더함
            }
        }
    }
}

❗️코드 설명

        boolean isNegative = false; // 음수니?
        int totalPlusValue = 0;
        while (true) {
        // 입력 문자의 ASCII코드 값.
        // 가령 '0'이 들어왔으면 숫자 0이 아니라 '0'의 ASCII 코드값인 48이다.
        int inputChar = System.in.read();

isNegative는 음수인지 양수인지를 판별하고('-' 문자열을 통해)
totalPlusValue는 문자열을 정수화시킨 값이다. 그리고 반복문을 통해 입력되는 문자를 정수로 계산해 계속 더해줄 것이다.

System.in.read() 메서드를 통해 문자를 계속 받아주고 아래 조건문을 통해 계속 비교한다.

         if (inputChar == ' ' || inputChar == '\n') { // 개행문자거나 공백이면 연산을 끊음
             return (isNegative)
                     ? -1 * totalPlusValue // 음수면 - 붙여서 반환
                     : totalPlusValue; // 양수면 그냥 반환
         } else if (inputChar == '-') { // 문자를 읽었는데 -가 붙어있으면 이 값은 음수임
             isNegative = true;
         } else {
             totalPlusValue = totalPlusValue * 10 + (inputChar - 48); // 기존 값을 10배하고 입력된 추가값을 파싱하여 더함
         }

입력된 문자열이 공백이거나 개행문자인 경우 함수를 종료,

isNegative가 참인지 거짓인지에 따라 음수 혹은 양수의 정수를 반환한다.

입력되는 문자열이 음수 부호('-')일 경우,

isNegative를 true로 바꿔준다.

아닐 경우 입력되는 문자를 계산해 totalPlusValue에 값을 누적해준다.

첫번째 if문에서 리턴이 안됐다면 정수 문자를 계속 받고 있는 것이므로 기존 계산된 값 * 10 + 현재 들어온 문자열을 정수로 계산한 값을 더해 계산해준다.

❗️조건

정수, 혹은 정수 배열만 가능하며 형식이 7 혹은 7 14 9 2 32 7 이런 식으로 공백을 기준으로 구분되어야 하며 [ ] , 와 같은 배열 구성 문자들은 별도의 조건 처리를 해줘야 한다.

❗️처리 예제

package fastIO;

import java.io.IOException;
import java.util.Arrays;

public class FastIO {
    public static void main(String[] args) throws IOException{
        int N = readInt();
        int[] testArr = new int[N];
        for (int i = 0; i < N; i++) {
            testArr[i] = readInt();
        }
        System.out.println("arr = " + Arrays.toString(testArr));
    }

    private static int readInt() throws IOException {
        boolean isNegative = false; // 음수니?
        int value = 0;
        while (true) {
            // 입력 문자의 ASCII코드 값.
            // 가령 '0'이 들어왔으면 숫자 0이 아니라 '0'의 ASCII 코드값인 48이다.
            int input = System.in.read();
            if (input == ' ' || input == '\n') { // 개행문자거나 공백이면 연산을 끊음
                return (isNegative)
                        ? -1 * value // 음수면 - 붙여서 반환
                        : value; // 양수면 그냥 반환
            } else if (input == '-') { // 문자를 읽었는데 -가 붙어있으면 이 값은 음수임
                isNegative = true;
            } else {
                value = value * 10 + (input - 48); // 기존 값을 10배하고 입력된 추가값을 파싱하여 더함
            }
        }
    }
}

❗️처리 결과

10
9 5 7 2 4 7 10000000 840 99999 1242
arr = [9, 5, 7, 2, 4, 7, 10000000, 840, 99999, 1242]

Process finished with exit code 0

참고로,

Fast I/O 에 대한 다양한 구현이 있는데 코드가 너무 길고 외우기 힘들어서 최대한 짧은 코드를 작성했다. Fast I/O에 대해 검색해보면 다양한 코드 예제들이 나온다. 찾아보고 싶다면 찾아보자..

✔️ Fast I/O 성능

경우에 따라선 BufferedReader가 빠르거나 더 유용할 수 있다.

또한 코딩테스트 문제 중 주어지는 테스트 케이스의 갯수가 주어지지 않으면 해당 Fast I/O를 사용하지 못한다.