[백준][TIP] 15552 번 빠른 출력

빠른 A+B

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (하단 참고)	8 MB	11385	5048	4117	48.135%

문제

본격적으로 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의 기타 여러 가지 팁을 볼 수 있다.

 

->>이 글

C

scanf/printf는 충분히 빠릅니다.

C++

• endl은 개행문자를 출력할 뿐만 아니라 출력 버퍼를 비우는 역할까지 합니다. 그래서 출력한 뒤 화면에 바로 보이게 할 수 있는데, 그 버퍼를 비우는 작업이 매우 느립니다. 게다가 온라인 저지에서는 화면에 바로 보여지는 것은 중요하지 않고 무엇이 출력되는가가 중요하기 때문에 버퍼를 그렇게 자주 비울 필요가 없습니다. 그래서 endl을 '\n'으로 바꾸는 것만으로도 굉장한 시간 향상이 나타납니다.
• cin.tie(NULL)은 cin과 cout의 묶음을 풀어 줍니다. 기본적으로 cin으로 읽을 때 먼저 출력 버퍼를 비우는데, 마찬가지로 온라인 저지에서는 화면에 바로 보여지는 것이 중요하지 않습니다. 입력과 출력을 여러 번 번갈아서 반복해야 하는 경우 필수적입니다.
• ios_base::sync_with_stdio(false)는 C와 C++의 버퍼를 분리합니다. 이것을 사용하면 cin/cout이 더 이상 stdin/stdout과 맞춰 줄 필요가 없으므로 속도가 빨라집니다. 단, 버퍼가 분리되었으므로 cin과 scanf, gets, getchar 등을 같이 사용하면 안 되고, cout과 printf, puts, putchar 등을 같이 사용하면 안 됩니다.

Java

BufferedWriter 외에도, StringBuilder로 출력을 모아 놓았다가 그 String을 System.out.println하는 방법도 있습니다.

Python

rstrip을 하라는 건 문자열 자체를 변수에 저장하고 싶을 때 얘기지, 개행문자가 맨 끝에 들어와도 int 변환이나 split()을 그대로 할 수 있습니다. 즉 int(sys.stdin.readline()), sys.stdin.readline().split() 이렇게 해도 아무 문제 없습니다. 참고로 이름이 꽤 길기 때문에 저는 input = sys.stdin.readline을 맨 처음에 함으로써 쓰는 편입니다.

Ruby

gets와 puts는 충분히 빠릅니다.

Go

bufio를 import하면 버퍼를 사용한 빠른 입출력이 가능합니다.

C#

StreamReader로 읽고, StringBuilder로 출력을 모아 놓았다가 그 String을 Console.WriteLine하는 방법이 있습니다. BufferedStream과 StringWriter로 조금 더 향상시킬 수 있는 것 같으나 자세한 것은 다른 분의 답변을 기다리겠습니다.

VB

StringBuilder로 출력을 모아 놓았다가 그 String을 Console.WriteLine하는 방법이 있습니다.

BOJ 의 여러가지팁

• 파이썬으로 재귀를 너무 깊이 들어가지 마세요. (Python) 기본 설정상 1000이 최대입니다. sys.setrecursionlimit으로 최대 깊이를 늘리거나, (메모리가 너무 부족한 문제일 경우) 아예 재귀 없는 풀이를 생각해 보세요.
• \b는 하나의 문자일 뿐, 정말로 출력했던 문자를 도로 지우는 문자가 아닙니다. 단지 화면에 내보낼 때만 지운 것처럼 보이게 할 뿐입니다. 출력했던 문자는 지울 수 없습니다.
• 부동소수점 자료형으로 정수를 저장하면 안 됩니다. 넓은 범위의 수를 나타내기 위해 정확도를 희생한 자료형입니다. 무슨 수든 정확하게 나타내는 마법의 자료형이 아닙니다.
• 입출력이 느리면 그것만으로도 시간초과가 날 수 있습니다. https://www.acmicpc.net/problem/15552
• '\n'으로 입력의 끝을 검사할 경우 문제가 생길 수 있습니다. 지금은 데이터의 끝에 '\n'가 반드시 들어오도록 되어 있지만, 오래된 데이터는 '\n'가 없는 경우가 있습니다. getchar나 fgets로 입력받을 때는 '\n'과 EOF를 모두 검사하는 것이 안전합니다.
• 널 문자는 하나의 문자로 취급되며, 널 문자와 공백은 다릅니다. 일부 컴퓨터에서 널 문자를 출력할 때 빈 칸이 출력되는데, 실제로는 엄연히 공백과 다른 하나의 문자입니다. 그래서 널 문자를 출력하지 말아야 되는 데 / 공백을 출력해야 되는데 널 문자를 출력하면 오답입니다.
• 알고리즘이나 내부 함수의 작동 원리와 시간복잡도를 숙지합시다.
• 1. C/C++: strlen은 O(N)입니다. memset은 0과 -1만 가능합니다. https://www.acmicpc.net/board/view/23217#comment-40375
• 2. Java: Linkedlist의 x번째 원소 찾기는 O(x)입니다.
• 3. Python: list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. 특히 list를 큐처럼 쓰면 절대로 안 됩니다. collections.deque를 써야 합니다.
• 4. 대부분의 언어: 배열 기반의 리스트 (C++ vector, string, Java ArrayList, String, Python list, str, ...)의 중간에 뭔가를 끼워넣고 빼는 건 O(N)입니다.
• 5. 알고리즘: DFS는 절대로 최단거리를 구해 주지 않습니다. 최단거리는 BFS입니다.
• 6. 알고리즘: 퀵소트를 직접 구현하면 O(N^2)이 걸리는 데이터를 손쉽게 만들 수 있습니다. 그냥 내장된 정렬 함수를 쓰세요.
• 7. 알고리즘: BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. BFS 문제에서 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.