[BOJ/Python, Java] 백준 11729번 - 하노이 탑 이동 순서

백준 #11729하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

 

Python ver.

def hanoi(n, start, temp, dest):
    global cnt
    if n == 0:
        return
    hanoi(n-1, start, dest, temp)
    route.append((start, dest))  # n번 원판 1 -> 3
    cnt += 1
    hanoi(n-1, temp, start, dest)


n = int(input())
cnt = 0  # 옮긴 횟수
route = []  # 원판 옮기는 장대 위치
hanoi(n, 1, 2, 3)
print(cnt)
for i in range(cnt):
    print(*route[i])

 

Java ver.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.IOException; 

public class Main  {
	static int cnt = 0;
	static ArrayList startRoute = new ArrayList();
	static ArrayList EndRoute = new ArrayList();
	
	public static void hanoi(int n, int start, int temp, int dest) {
		if (n == 0) return;
		
		hanoi(n-1, start, dest, temp);
		startRoute.add(String.valueOf(start));
		EndRoute.add(String.valueOf(dest));
		cnt++;
		hanoi(n-1, temp, start, dest);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		hanoi(n, 1, 2, 3);

		sb.append(cnt).append('\n');
		for (int i = 0; i < startRoute.size(); i++) {
			sb.append(startRoute.get(i)).append(" ").append(EndRoute.get(i)).append('\n');
		}
		
		System.out.println(sb);
	}  // end of main
}  // end of class

 

---

• System.out.println 에서 + 로 문자열 이어서 출력하면 새로운 객체를 생성해서 출력하는 거라 시간이 오래 걸린다! SringbBuilder를 이용하여 출력할 문자열들을 담아서 한 번에 출력해주자!

StringBuilder sb = new StringBuilder();
sb.append(cnt).append('\n');
for (int i = 0; i < startRoute.size(); i++) {
	sb.append(startRoute.get(i)).append(" ").append(EndRoute.get(i)).append('\n');
}
		
System.out.println(sb);