문제를 풀면서
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(목적지) 이렇게 세 개다.
- N단계라고 칠 때, N-1단계만큼을 2위치로 이동하고 1->3 한 다음에 2위치에 있는 N-1단계를 3으로 하면 된다. (그래서 최소횟수가 위와 같다)
- 아무튼 그렇게 완성을 했는데, 분명 문제는 없는 것 같은데... "시간초과"가 떴다. 그래서... 빠른 입출력을 공부해보자, 싶어서 구글링해서 아래와 같이 작성해봤다.
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);
}
}
- 빗질정렬을 시도해보면서 빠른입출력을 맛만 봤었는데, 그땐 실패했었다... (아직 이유를 잘 모르겠다ㅜㅠ) 하지만 여기선 성공했다. 그래서 참... 뿌듯했다.
- 특별한 건 없고 모든 입출력이 필요한 메서드에 예외처리를 해줘야 한다는 정도는 주의해야 할 것 같고...
- 아무튼 같은 코드에서 입출력 부분만 손봐줬는데, 나는 빠른지 잘 모르겠어서 그냥 제출을 해봤는데 됐다.
- 그래~서? 녹화를 해서 시간을 재봤다.
'PS - BOJ' 카테고리의 다른 글
1138 - 한 줄로 서기, 1032 - 명령 프롬프트 (0) | 2022.01.23 |
---|---|
1124 - 언더프라임 (0) | 2022.01.23 |
10872 - 팩토리얼, 1065 - 한수 (0) | 2022.01.22 |
11653 - 소인수분해 (0) | 2022.01.22 |
8958 - OX퀴즈, 1712 - 손익분기점 (0) | 2022.01.22 |