6번 빠른 A+B

문제

본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. 

 

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다. 

 

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다. 

 

Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다. 단, 이때는 맨 끝의 개행문자까지 같이 입력받기 때문에 문자열을 저장하고 싶을 경우. rstrip()을 추가로 해 주는 것이 좋다. 

 

또한 입력과 출력 스트림은 별개이므로, 테스트케이스를 전부 입력받아서 저장한 뒤 전부 출력할 필요는 없다. 테스트케이스를 하나 받은 뒤 하나 출력해도 된다. 자세한 설명 및 다른 언어의 경우는 이 글에 설명되어 있다. 이 블로그 글에서 BOJ의 기타 여러 가지 팁을 볼 수 있다.

 

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T 줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다.

 

출력

각 테스트케이스마다 A+B를 한 줄에 하나씩 순서대로 출력한다.

 

입출력 시 발생할 수 있는 문제를 해결하여 테스트케이스를 통과해야 하는 문제이다.

친절하게 문제에서 해결방법을 제시해 주었기 때문에 위 방법들을 고려하여 테스트케이스를 통과해 본다.

 

C++

오답

#include <iostream>
using namespace std;
int main(){
    int t;
    cin >> t;
    for (int i = 0; i < t; i++){
        int a, b;
        cin >> a >> b;
        cout << a + b << "\n";
    }
    return 0;
}

 

확인을 위해 제시된 방법을 사용하지 않고 코드를 작성하여 테스트해 보니 '시간 초과' 결과가 나타난다.

 

위 방법들을 사용해서 다시 풀어본다.

 

#include <iostream>
using namespace std;
int main(){
    int t;
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> t;
    for (int i = 0; i < t; i++){
        int a, b;
        cin >> a >> b;
        cout << a + b << "\n";
    }
    return 0;
}

 

cin.tie(NULL)은 cin과 cout의 묶음을 풀어주는 기능을 한다.

기본적으로 cin으로 읽을 때 먼저 출력 버퍼를 비우는 작업이 먼저 처리되는데 이 작업을 통해서 출력이 즉시 화면에 표시되도록 한다. 하지만 이렇게 수만 번의 입력과 출력이 반복해서 처리되는 작업에서는 출력 버퍼를 비우는 작업은 고려하지 않아도 되기 때문에 테스트 케이스를 통과하기 위해서는 이런 부가적인 작업이 발생하지 않도록 해야 타임오버가 되지 않는다.

 

ios_base::sync_with_stdio(false)는 C와 C++의 버퍼를 분리한다.

C++은 C의 기능을 포함하고 있으므로 cin과 cout 사용 시 C의 입출력 라이브러리인 stdin, stdout과 연결된 스트림 객체 상태이다. 따라서 sync_with_stdio(false)를 선언하면 cin/cout은 더 이상 stdin/stdout과 동기화되지 않기 때문에 C++의 스트림 입출력 성능이 향상될 수 있지만 비활성화된 상태에서는 C의 scanf, printf와 함께 사용 시에는 문제가 발생한다.

 

개행문자 endl 은 줄 바꿈을 출력할 뿐만 아니라 출력 버퍼를 비우는 역할까지 하기 때문에 이 작업 역시 테스트케이스를 실행하게 되면 속도를 느리게 하기 때문에 단순 줄 바꿈만 하는 \n 개행문자를 사용하는 것이 속도측면에서 유리하다.

 

C#

C#의 경우 문제에서 해결방법이 제시되지 않아서 추가 정보글의 설명을 먼저 읽어 보았다.

Console.Write, WriteLine은 사용할 때마다 화면으로 내보내는 작업인 flush(C++의 출력버퍼를 비우는 작업)이 발생하는데 해결 방법으로는 StringBuilder에 출력할 내용을 모아둔 뒤 한 번에 출력하거나 auto flush를 하지 않는 output stream을 Console에 연결하는 방법이 있다.

 

StringBuilder

using System;
using System.Text;
class Program{
    static void Main(string[] args){
        StringBuilder sb = new StringBuilder();
        int t = int.Parse(Console.ReadLine());
        for (int i = 0; i < t; i++){
            int a, b;
            string input = Console.ReadLine();
            string[] arr = input.Split(' ');
            a = int.Parse(arr[0]);
            b = int.Parse(arr[1]);
            sb.AppendLine((a+b).ToString());
        }
        Console.WriteLine(sb.ToString());
    }
}

 

StringBuilder를 사용해서 문자열을 저장하고 한 번에 출력하여 flush로 인한 속도 저하를 방지한다. string이 아닌 StringBuilder를 사용하는 이유는 문자열 연결 작업에서 불변 특성을 가지기 때문에 더 효율적인 처리가 가능하고 string의 문자열을 추가하는 + 연산 작업은 새로운 문자열 객체가 생성되고 이 과정에서 메모리 사용량과 실행 시간이 증가할 수 있다.

 

Append : 문자열만 추가한다.

AppendLine : 문자열 추가하고 줄 바꿈 문자를 자동으로 추가한다.

AppendFormat : 형식 문자열을 추가한다.

 

output stream

using System;
class Program{
    static void Main(string[] args){
        int t = int.Parse(Console.ReadLine());
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()));
        for (int i = 0; i < t; i++){
            int a, b;
            string input = Console.ReadLine();
            string[] arr = input.Split(' ');
            a = int.Parse(arr[0]);
            b = int.Parse(arr[1]);
            Console.WriteLine(a + b);
        }
        Console.Out.Flush();
    }
}

 

출력 전 자동으로 flush 하는 기능을 비활성화한다. 이 기능을 사용하고 나서 코드 종료 전에 출력 버퍼를 지우는 Flush()를 호출해 주어야 한다.

 

추가로 StreamReader와 StreamWriter를 사용하는 방법

using System;
using System.IO;

class Program {
    private const int bufferSize = 131072;
    public static readonly StreamReader input = new(new BufferedStream(Console.OpenStandardInput(), bufferSize));
    public static readonly StreamWriter output = new(new BufferedStream(Console.OpenStandardOutput(), bufferSize));

    static void Main(string[] args) {
        int t = int.Parse(input.ReadLine());

        for (int i = 0; i < t; i++) {
            string[] arr = input.ReadLine().Split(' ');
            int a = int.Parse(arr[0]);
            int b = int.Parse(arr[1]);
            output.WriteLine(a + b);
        }
        output.Flush();
    }
}

 

input과 output을 구현하여 처리한다.

마찬가지로 코드가 종료되기 전에 출력버퍼를 비워준다.

 

Python

파이썬에서는 입력을 받는 함수인 input 대신 sys.stdin.readline을 사용하면 된다. 이 경우 문자열 끝에 개행문자까지 같이 입력받게 되므로. rstrip()으로 문자열만 저장하도록 한다.

import sys
t = int(input())
for i in range(t):
    input_str = sys.stdin.readline().rstrip()
    arr = input_str.split(' ');
    a = int(arr[0])
    b = int(arr[1])
    print(a+b)

 

먼저 sys를 사용하기 위해서 모듈을 임포트 해준다.

 

입력받은 문자열을 저장할 때 변수명을 str로 사용했었는데 이 키워드는 파이썬에서 내장 타입으로 사용되고 있기 때문에 문제가 되는 걸 방지하기 위해서 input_str로 사용했다.

 

input을 사용하게 되면 시간초과가 발생한다. 

sys.stdin.readline()은 C 표준 라이브러리의 fgets 함수에 가깝게 동작하는데 이는 입력 스트림에서 한 줄을 읽어오고 문자열로 반환한다. 따라서 직접적으로 표준 입력에서 빠르게 읽어오기 때문에 input보다 더 빠른 속도로 처리할 수 있다.

 

print의 경우 기존 방식을 사용해도 문제가 없다. print 함수는 기본적으로 출력 버퍼링을 사용하긴 하지만 매번 호출할 때마다 버퍼를 flush 하지 않는 게 기본 상태이다. 그리고 이를 수동으로 flush 하도록 변경할 수 있다.

print("Something print", flush=true)

 

Node.js

fs

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
const t = parseInt(input[0], 10);
const output = [];

for (let i = 1; i <= t; i++) {
    const [a, b] = input[i].split(' ').map(Number);
    output.push(a + b);
}

process.stdout.write(output.join('\n'));

 

반복문에서 출력할 정보를 저장해 놓고 마지막에 한 번에 출력한다. 

 

위)console.log

 

이때 console.log를 사용해도 성공했는데 process.stdout.write를 사용하는 게 조금 더 빠르게 처리되었다.

 

 

readline

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let input = [];
let lineIndex = 0;
rl.on('line', (line) => {
    input.push(line);
});
rl.on('close', () => {
    const t = parseInt(input[lineIndex++], 10);
    let output = [];
    for (let i = 0; i < t; i++) {
        const [a, b] = input[lineIndex++].split(' ').map(Number);
        output.push(a + b);
    }
    process.stdout.write(output.join('\n'));
});

 

readline 사용한 게 기본적으로 fs보다 느렸다.

아래)console.log

 

앞으로 문제들은 단순히 해결하는 것뿐만 아니라 더 나은 방법에 대해서도 알 필요가 있는 내용들이 나올듯하다.

728x90
반응형
저작자표시

'Coding Test' 카테고리의 다른 글

백준 코딩테스트 #17. 반복문 (11, 12)  (0) 2024.08.01
백준 코딩테스트 #16. 반복문 (7~10)  (0) 2024.08.01
백준 코딩테스트 #14. 반복문 (4, 5)  (0) 2024.07.31
백준 코딩테스트 #13. 반복문 (1 ~ 3)  (0) 2024.07.29
백준 코딩테스트 #12. 조건문 7  (0) 2024.07.26

+ Recent posts

티스토리툴바