[Algorithm] println과 StringBuilder 속도 차이

https://www.acmicpc.net/problem/2493

println을 쓰니까 시간이 3280ms로 너무 느려서 StringBuilder로만 바꿔줬더니 시간이 924ms로 엄청나게 단축되었다.

마지막 System.out.println(sb); 문도 BufferedWriter를 써서 변경해주었더니 876ms로 더 단축되는걸 볼 수 있었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_2493_탑{
	private static class Tower{
		int h;
		int idx;
		
		public Tower(int h, int idx) {
			this.h = h;
			this.idx = idx;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

		Stack<Tower> s = new Stack<Tower>();
		int n = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine(), " ");

		for (int i = 1; i <= n; i++) {
			int cur = Integer.parseInt(st.nextToken());

			while(!s.isEmpty()) {
				if (s.peek().h < cur) {
					s.pop();
				}else  {
					sb.append(s.peek().idx + " ");
					break;
				}
			}

			if (s.isEmpty()) {
				sb.append(0 + " ");
			}
            
			s.push(new Tower(cur, i));
		}
		out.write(sb.toString());
		out.flush();
		out.close();
	}
}

StringBuilder가 빠른 이유를 찾아보았는데 String은 immutable한 객체로 값을 수정하면 새로운 객체를 만들어내서 메모리와 시간을 잡아먹는다고 한다. (실제로 메모리도 129008KB -> 101988KB 로 줄었다.)

StringBuilder를 사용하게 되면 같은 주소에 값만 수정하므로 훨씬 빠르다.

예를 들어 for문 10000번을 돌면서 10000줄의 문자열을 출력한다고 가정하면 System.out.println()은 10000번의 String을 선언하고 메모리를 잡아먹지만 StringBuilder에 sb.append()를 하면 하나의 주소의 sb에 값만 수정하므로 훨씬 빠르다.

Reference

• https://cantcoding.tistory.com/38