백준 11729번 문제 하노이 탑 이동 순서 리뷰

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

하노이탑 문제는 유명한 '재귀 문제'인데 N을 1에서 부터 4 정도까지 증가 시켜보면서

• Hanoi(n) = 2 × Hanoi(n-1) + 1 << 식을 구해내는게 중요한 것 같다.

처음 문제 풀 때 StringBuffer를 사용하지않고 String으로 더해서 값을 구했더니
String(tmp)에 값을 더해줄때마다 새로 생성함으로 각 String의 주소값이 stack에 쌓이고 class들은 garbage collector가 호출되기 전까지 heap에 지속적으로 쌓이게 되는걸 몰랐다.. 메모리 측면에서도 치명적이고 속도 또한 시간제한에 걸렸다.

String대신 StringBuffer 클래스를 사용함으로서 tmp의 값이 변화해도 같은 메모리에 append하는 방식이라 클래스가 생성됨으로서 method들과 variable들이 생성되는 시간이 추가적으로 들지않아 시간제한에 안걸린것 같다.

• StringBuffer와 StringBuilder의 차이는 둘 다 변경가능한 문자열이지만 StringBuilder는 synchronization이 적용되지 않고, StringBuffer는 적용되어 multiple thread에서 안전한 클래스라고 한다.
• 자바 알고리즘에서 입/출력에서 시간 단축하는 방법
  입력 : Scanner 대신 BufferedReader를 사용한다.
  예시 : BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  출력 : System.out.print 대신 BufferedWriter를 사용한다.
  예시 : static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));