쉬운 문제라도 문제를 푸는 방법은 다양합니다.
더 명확하고 깔끔한 문제 해결 방법을 아신다면 자유롭게 말씀해주세요.
프로그래머스 12946 하노이의 탑
프로그래머스 저작권을 침해하지 않기 위해
문제 보시고 싶으시면 버튼을 눌러주세요.
답변 형식
원판의 갯수 n을 받아 최소한의 이동으로 n개의 원판을 1번 고리에서 2번 고리로 옮길 수 있는 방법 return 합니다.
return은 이중 배열로 int[이동 횟수]=[이동시작점,도착점]입니다.
주의 사항
제가 푼 방식은 테스트케이스 1개가 틀리지만 본 채점에서는 100점입니다.
다른 분들도 채점은 만점이지만 테스트케이스 오류가 나는 경우에 대해 말씀을 해주셔서
이번 문제에서는
테스트케이스 만점을 위해 코드를 고칠 필요가 없다고 말씀 드립니다.
풀이 조건
하노이의 탑은 손으로 문제를 풀며 문제를 푸는 방법을 알고, 그대로 코딩하면 되는 신기한 문제였습니다.
문제를 푸는 방법은 알았는데 설마 그대로 코딩이 될까라고 고민하셨다면 정답입니다.
원반이 5개라면
(1) 마지막 5번 원반을 3번 고리에, 1-4까지 원반을 2번 고리 놓습니다.
(2) 그리고 다시 1-4번 원반을 3번 원반으로 옮깁니다.
(2)의 과정은 원반이 4개일 때 하노이의 탑 프로그래밍을 돌릴 때와 동일합니다. 단지 원반이 있는 고리가 1번에서 2번 고리일 뿐입니다.
이 과정의 반복입니다.
재귀 알고리즘과 하노이의 탑이라는 하나의 알고리즘을 공부하기 좋았습니다.
추가 참고 자료
JAVA 정답
import java.util.*;
// 문제는 정답이지만
// 테스트 케이스는 오류임. – 테스트케이스와 정답은 같지만 한개가 틀림.
class Solution {
public int[][] solution(int n) {
List<Integer[]> answer_list = new ArrayList<>();
hanoi(answer_list, n, 1,3,2);
int[][] answer = new int[answer_list.size()][2];
for(int i=0; i<answer.length; i++) {
Integer[] now = answer_list.get(i);
answer[i][0] = now[0];
answer[i][1] = now[1];
}
return answer;
}
void hanoi(List<Integer[]> answer_list, int n, int start, int to, int via){
if(n==1) {
move(answer_list, 1, start, to);
} else {
hanoi(answer_list, n–1, start, via, to);
move(answer_list, n, start, to);
hanoi(answer_list, n–1, via, to, start);
}
}
void move(List<Integer[]> answer_list, int n, int start, int to) {
Integer[] answer = {start, to};
answer_list.add(answer);
}
}
JAVA 정답 해설
import java.util.*;
// 문제는 정답이지만
// 테스트 케이스는 오류임. – 테스트케이스와 정답은 같지만 한개가 틀림.
class Solution {
public int[][] solution(int n) {
List<Integer[]> answer_list = new ArrayList<>();
hanoi(answer_list, n, 1,3,2);
int[][] answer = new int[answer_list.size()][2];
for(int i=0; i<answer.length; i++) {
Integer[] now = answer_list.get(i);
answer[i][0] = now[0];
answer[i][1] = now[1];
}
return answer;
}
void hanoi(List<Integer[]> answer_list, int n, int start, int to, int via){
if(n==1) {
move(answer_list, 1, start, to);
} else {
hanoi(answer_list, n–1, start, via, to);
move(answer_list, n, start, to);
hanoi(answer_list, n–1, via, to, start);
}
}
void move(List<Integer[]> answer_list, int n, int start, int to) {
Integer[] answer = {start, to};
answer_list.add(answer);
}
}