백준 문제에서 Java의 표준 입출력이 시간 초과가 나는 이유..

백준에서 코테 문제를 풀다보면 느끼겠지만, 입/출력 쪽에서 시간 초과가 자주 발생한다. 

(분명 알고리즘은 맞았는데, 계속 시간초과가 나면 대부분 이 문제다..)

 

각각 어떤 곳에서 문제가 발생하는지 파헤쳐보자.

 

입력 문제

입력에 문제가 생기는 경우는 대부분 Scanner를 써서 여러번 next()나 nextInt()으로 가져오는 경우다.

 

입력에 문제가 생겼던 문제는 탑 이었다.

 

 

50만번은 딱히 많아보이지 않는 갯수이다. N번 정도는 그냥 하면 되는거 아냐? 라고 생각할 수 있겠지만

 

next의 코드를 따라가보면 문제가 있다는 걸 알 수 있다.

public String next(Pattern pattern) {
    ensureOpen();
    if (pattern == null)
        throw new NullPointerException();

    modCount++;
    // Did we already find this pattern?
    if (hasNextPattern == pattern)
        return getCachedResult();
    clearCaches();

    // Search for the pattern
    while (true) {
        String token = getCompleteTokenInBuffer(pattern);
        if (token != null) {
            matchValid = true;
            skipped = false;
            return token;
        }
        if (needInput)
            readInput();
        else
            throwFor();
    }
}

next는 두 가지 문제가 있는데, 하나는 getCompleteTokenInBuffer 패턴 검사를 한다는 점과 readInput()에서 빈번하게 I/O가 발생할 수 있다는 점이다.

 

사실 패턴 검사는 다른 방식으로 입력을 받아도, StringTokenizer에서 해줘야하는 경우가 많다.

 

그래서 패턴 검사는 큰 문제가 아닐 수 있지만, I/O가 빈번하게 일어나는 건 큰 문제다.

(왜 문제인지는 아래에서 설명한다)

 

그래서 nextInt를 반복문으로 호출하는 방식보다는 한번에 싹 읽어와서 버퍼에 저장해두는 방식인 BufferedReader방식이 조금 더 권장될 것 같다. 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

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

 

물론, nextInt()를 사용해도 상관없는 경우도 많지만, 어디가 틀렸는지 확인하기 싫으면 BufferReader를 이용하자.

 

분명 알고리즘은 맞았다니까...

 

출력 문제

출력은 System.out.print.ln을 여러번 찍게 되는 경우 문제가 발생한다.

 

가장 처음 문제가 생겼던건 별 찍기 - 10 이었다.

 

딱봐도 출력해야하는 양이 많다.

 

 

결국엔 풀긴 했지만 처음에 시간 초과가 났을 때는 어리둥절했다.

 

주어진 조건의 최대인 3^7(2187)까지도 내 로컬에서는 잘 동작했기 때문이다.

 

다른 사람들과 비교해보고 원인은 비교적 쉽게 발견할 수 있었다.

 

출력을 System.out.println()으로 했기 때문이었다.

 

왜 문제가 발생하는지 알아보자.

 

원인을 알아보기 위해서는, println 매서드부터 뜯어볼 필요가 있다.

public void println(int x) {
    if (getClass() == PrintStream.class) {
        writeln(String.valueOf(x));
    } else {
        synchronized (this) {
            print(x);
            newLine();
        }
    }
}

println 매서드는 PrintStream 클래스의 매서드인 println을 호출한다.

 

그리고 println을 타고 들어가보면, writeln으로 이어진다.

(print는 writeln에서 newLine()만 제외하고 동작이 거의 같다)

private BufferedWriter textOut;

private void writeln(String s) {
    try {
        synchronized (this) {
            ensureOpen();
            textOut.write(s);
            textOut.newLine();
            textOut.flushBuffer();
            charOut.flushBuffer();
            if (autoFlush)
                out.flush();
        }
    }
    catch (InterruptedIOException x) {
        Thread.currentThread().interrupt();
    }
    catch (IOException x) {
        trouble = true;
    }
}

타고 내려가보면 결국 system.out.println도 BufferedWriter를 이용해 출력하는 것을 알 수 있다.

 

다만, 버퍼에 데이터를 쌓진 않는다.

 

이럴 경우, 발생하는 문제는 반복적으로 flush()를 하기 때문에, 빈번한 I/O가 발생하게 된다는 것이다.

 

출력할 때는 아래와 같이 BufferedWriter에 쌓고 마지막에 한번 출력하도록 하자.

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

bw.write(num + " ");
bw.newLine();

bw.flush(); 
bw.close();

 

I/O를 줄여야 하는 이유

I/O 작업은 CPU에 컨텍스트 스위칭을 발생시키고, 반복적인 컨텍스트 스위칭은 엄청난 오버헤드를 발생시킨다.

 

그래서 코딩 테스트에서 입/출력량이 많은 경우

 

BufferedReader/BufferedWriter 클래스와 같이 buffer에 데이터를 쌓은 후 마지막에 flush를 해서 컨텍스트 스위칭의 횟수를 줄이는 방식을 사용해야 한다.

 

물론 buffer에 쌓이는 데이터가 지나치게 많은 경우도 문제가 될 수 있으니 조심할 필요가 있으나

 

상대적으로는 자주 발생하지 않는 문제다.

 

어떤 곳에서는 synchronized 문제라고 지적하는 곳이 있는데, 이건 딱히 문제가 될게 없다.

 

어차피 코딩 테스트는 멀티 쓰레드로 동작하는 환경이 아닌데,

 

thread safe용으로 syncronized를 둔건 아무런 문제가 되지 않는다.

 

마치며

개인적인 생각이지만, 백준 쪽 코딩테스트는 입/출력이 어떻게 보면 가장 큰 진입장벽인 것 같다.

 

특히 I/O의 개념과 버퍼, 컨텍스트 스위칭 같은건 비전공자에게는 이해하기 어려운 부분이라 생각한다.

 

현업에서도 자주 발생하는 일 중 하나가 무심코 System.out.println을 코드에 넣어버리는 경우가 있는데,

 

이럴 경우 갑자기 api의 속도가 느려지는 경우가 발생한다.

 

조심하도록 하자.