11729 - 하노이 탑 이동 순서 (빠른 입출력!!)

문제를 풀면서

Scanner, System.out.println을 사용한 것과

빠른 입출력, BufferedReader, BufferedWriter를 사용한 코드를 비교해봤다.

11729

재귀 단계
하노이 탑 이동 순서

• 규칙은 하노이 탑 게임과 같다.
• 최초 탑 높이 N 입력. > 최소 이동 횟수 K 출력 > 이동 순서 출력("1 3" : 1위치 가장 위 원판을 3위치로 이동)

1) 처음엔 이렇게 짰다.

import java.util.Scanner;

public class bj11729plus_0122 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        System.out.println(hanoi(N));
        moveHanoi(N, 1, 3);
    }

    static int hanoi(int N) {
        if (N == 1) {
            return 1;
        }
        N = 1 + 2 * hanoi(N - 1);
        return N;
    }

    static void moveHanoi(int N, int now, int goal) {
        int temp = 6 - now - goal;
        if (N == 1) {
            System.out.printf("%d %d\n", now, goal);
            return;
        }

        moveHanoi(N - 1, now, temp);
        System.out.printf("%d %d\n", now, goal);
        moveHanoi(N - 1, temp, goal);

    }
}

• 실버1 단계인 거에 비해 적당히 어려웠다. 하지만 하노이 탑을 어렸을 때 폰게임으로 많이 해봐서 익숙해서... 기억을 더듬어가며 코드를 짰다.
• 일단 재귀를 써서 최소 횟수를 구하는데, "(N레벨 최소횟수) = 1+ 2*(N-1레벨 최소횟수)"인 점을 이용해서 구현했다. 그게 hanoi()고...
• 다음은 이동 순서를 출력하는 moveHanoi()인데
  • N단계라고 칠 때, N-1단계만큼을 2위치로 이동하고 1->3 한 다음에 2위치에 있는 N-1단계를 3으로 하면 된다. (그래서 최소횟수가 위와 같다)
    • 여기서 중요한 건, N단계에 대한 출력을 할 때 시작점과 목적지를 매개변수로 입력가능하게 해야 한다는 점이다. 그래서 매개변수가 N(단계), now(시작), goal(목적지) 이렇게 세 개다. 
• 아무튼 그렇게 완성을 했는데, 분명 문제는 없는 것 같은데... "시간초과"가 떴다. 그래서... 빠른 입출력을 공부해보자, 싶어서 구글링해서 아래와 같이 작성해봤다.

2) 빠른 입출력을 써서 이렇게 짰다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class bj11729_0122 {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());

        bw.write(hanoi(N) + "\n");

        moveHanoi(N, 1, 3);

        bw.flush();
        bw.close();
    }

    static int hanoi(int N) {
        if (N == 1) {
            return 1;
        }
        N = 1 + 2 * hanoi(N - 1);
        return N;
    }

    static void moveHanoi(int N, int now, int goal) throws IOException {
        int temp = 6 - now - goal;
        if (N == 1) {
            bw.write(now + " " + goal + "\n");
            return;
        }

        moveHanoi(N - 1, now, temp);
        bw.write(now + " " + goal + "\n");
        moveHanoi(N - 1, temp, goal);

    }
}

• 빗질정렬을 시도해보면서 빠른입출력을 맛만 봤었는데, 그땐 실패했었다... (아직 이유를 잘 모르겠다ㅜㅠ) 하지만 여기선 성공했다. 그래서 참... 뿌듯했다.
• 특별한 건 없고 모든 입출력이 필요한 메서드에 예외처리를 해줘야 한다는 정도는 주의해야 할 것 같고...
• 아무튼 같은 코드에서 입출력 부분만 손봐줬는데, 나는 빠른지 잘 모르겠어서 그냥 제출을 해봤는데 됐다.

 

• 그래~서? 녹화를 해서 시간을 재봤다.