Java 언어로 알고리즘 문제 풀이 시 시간초과 문제

시간초과가 주로 발생하는 부분

Java의 입력: Scanner 대신 BufferedReader 사용

#자바 표준 입출력 라이브러리 사용법 정리 → Scanner보다 시간 단축 !!

BufferedReader는 데이터를 사용자가 요청할 때마다 매번 읽어오는 것이 아닌, 버퍼에 일정량만큼 보관해두었다가 한 번에 읽는다. 따라서 속도가 향상하고 시간 부하를 줄일 수 있다.

Scanner	BufferedReader
space를 모두 경계로 인식	enter(’\n’)만을 경계로 인식
가공이 쉬움	다량의 데이터를 입력받는 경우 효율이 좋음
- 효율성이 낮음 - 시간이 오래 걸림	- Scanner와 달리 Exception 처리가 자체적으로 되어 있지 않아 따로 처리가 필요함 - 한 줄 안에서 공백을 기준으로 나눠야 한다면 StringTokenizer 를 따로 사용해야 함

사용 방법

1. main 클래스에 "throws IOException" 추가

2. 입력값 셋팅

3. 변수에 입력 값 저장하기

[줄 기준 입력]

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); -> 라이브러리 가져오기

[공백 기준 입력]

StringTokenizer st = new StringTokenizer(br.readLine());
String[] line = br.readline().split(" ");
int[] arr = new int[line.length];

for (int i=0; i<line.length; i++) {
		arr[i] = Integer.parseInt(line[i]);  // 정수형일 때
}

while((tmp = br.readLine()) != NULL){    // 전체 입력 저장할 때
		str += tmp + "\n";
}

• BufferedReader, StringTokenizer은 기본적으로 String으로 읽음 => 다른 자료형에 대해서는 형 변환 필요
• parseInt, parseDouble, parseFloat 등 int, double, float형 가져오기
• 공백 기준으로 입력 받다가 줄 바꿈하려면? st = new StringTokenizer(br.readLine(), " ");
  

Java의 출력: System.out.println() 대신 StringBuilder / BufferedWriter 사용

System.out.println() 의 내부

public void println(String x) {
     synchronized (this) {
         print(x);   // 출력
         newLine();  // 새로운 줄 생성
     }
}

synchronized block 으로 씌워져 있어 동기화가 이루어진다. 동기화는 하나의 프로세스마다 존재하는 하나 이상의 쓰레드에서 공유 데이터가 존재하는 경우, 작업 중인 쓰레드가 하나라도 있으면 다른 쓰레드의 접근을 막는다. 이때 동기화는 접근을 막음으로써 쓰레드들의 대기시간이 발생하게 되는데 이는 오버헤드를 불러오게 된다.

즉, System.out.println 에는 동기화가 적용되어 호출만으로 오버헤드가 따르게 된다.

이러한 이유로 프로젝트 개발 시 로그를 sout 으로 남기는 것을 비권장한다.

❗ ***오버헤드(overhead)**란 ?*

어떤 처리를 하기 위해 들어가는 간접적인 처리 시간, 메모리 등

예시

• A라는 처리를 단순하게 실행한다면 10초 걸리는데, 안전성을 고려하고 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초가 된다.
• B를 개선해 B'라는 처리를 한 결과, 처리시간이 12초가 되었다면, 이 경우 오버헤드가 3초 단축되었다고 말한다.

StringBuilder 클래스를 사용하면?

StringBuilder sb = new StringBuilder();
sb.append("출력할내용\n");
sb.append("출력할내용").append("\n");   // 위 코드보다 개행을 나누어서 append 하는 것이 시간적으로 더 빠르다

StringBuilder (Java Platform SE 7 )

StringBuilder 클래스 공식 문서

BufferedWriter 클래스를 사용하면?

write()	출력할 내용을 버퍼에 담는다
flush()	버퍼를 비워내는 동시에 콘솔에 출력한다
close()	출력이 모두 끝나면, 스트림을 닫는다

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  // IOException 예외처리 필요
bw.write("Hello World");
bw.flush();
bw.close();

참고 자료

https://mygumi.tistory.com/83

https://zzinise.tistory.com/71

https://steady-coding.tistory.com/184