오늘의 학습내용
- 재귀함수
- 연결리스트 배열로 변환
공부한 내용
문제를 처음 보자마자 생각한건 마지막 원판의 크기가 가장 크므로 그 이전까지의 원판을 모두 다른 기둥으로 옮긴 후 마지막 원판을 3번째 기둥으로 옮긴다고 생각했다. 이를 위해 처음에는 stack으로 구현했었다. 그래서 생각했던 방법은 3개의 기둥을 모두 stack 자료구조로 구현한 후 다음과 같은 구조로 구현을 생각했다.
1) n개가 있다고 하면 (n-1)까지 1-> 2 로 옮김
2) 마지막 n번째 1 -> 3 으로 옮김
3) 1~(n-1) 까지의 원판들이 잇으면 (n-2)까지 2->1 로 옮김
4) 마지막 (n-1)번째 2 -> 3 으로 옮김
... 이런식으로 empty 가 아닐때까지 반복
Stack<Integer> A = new Stack<>();
Stack<Integer> B = new Stack<>();
Stack<Integer> C = new Stack<>();
while(!A.isEmpty()){
if(A.size()==1) {
C.push(A.pop());
while(!B.isEmpty()){
if(B.size()==1){
C.push(B.pop());
break;
}else{
A.push(B.pop());
}
}
}else{
B.push(A.pop());
}
}물론 이렇게 구현한 코드로는 문제에 주어진 2개의 원판 테스트케이스를 만족하지만 나머지에 대해서 실패를 했다. 코드를 다시 생각해보면 위와 같은 방식은 크기가 더 큰 원판이 작은 원판보다 위에 있을수도 있는 방법이기에 방법이 실패할 수도 있다.
이런 상황에서 생각해야 하는 방법은 재귀함수 이다. 그러면 재귀함수를 왜 써야할까?
문제를 다시 생각해보면 원판이 모두 n개 있다고 하자. 그리고 n개의 원판을 다른 기둥으로 옮기는 것을 Hanoi(n)이라고 하면 다음의 재귀가 구현된다.
1) n번째 원판을 제외한 1~(n-1)번째 원판은 2번 기둥으로 이동 : Hanoi(n-1)
2) n번째 원판은 3번 기둥으로 이동
3) 1~(n-2)번째 원판은 1번기둥으로 이동 : Hanoi(n-2)
...
결국 이를 재귀로 구현해보면 n개의 원판을 시작점과 끝점 그리고 경유하는 지점을 파라미터로 두고 구현할 수 있다.
public static void Hanoi(int n, int start, int mid, int to){
// 이동할 원반의 수가 1개인 경우
if(n == 1){
result.add(new int[] {start, to});
return;
}
// n-1개의 물건을 A -> B로 이동
Hanoi(n-1, start, to, mid);
// 1개의 물건을 A -> C 로 이동
result.add(new int[] {start, to});
// n-1개의 물건은 B -> C로 이동
Hanoi(n-1, mid, start, to);
}오늘의 회고
문제
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
내 풀이
import java.io.*;
import java.util.*;
class Solution {
static LinkedList<int[]> result = new LinkedList<>();
public static int[][] solution(int n){
int[][] answer = {};
Hanoi(n, 1, 2, 3);
answer = linkedListToArray(result);
return answer;
}
public static void Hanoi(int n, int start, int mid, int to){
// 이동할 원반의 수가 1개인 경우
if(n == 1){
result.add(new int[] {start, to});
return;
}
// n-1개의 물건을 A -> B로 이동
Hanoi(n-1, start, to, mid);
// 1개의 물건을 A -> C 로 이동
result.add(new int[] {start, to});
// n-1개의 물건은 B -> C로 이동
Hanoi(n-1, mid, start, to);
}
public static int[][] linkedListToArray(LinkedList<int[]> linkedList) {
// LinkedList의 크기로 int[][] 배열을 생성
int size = linkedList.size();
int[][] array = new int[size][];
// LinkedList의 각 int[]를 int[][] 배열에 복사
for (int i = 0; i < size; i++) {
array[i] = linkedList.get(i);
}
return array;
}
}다른 사람 풀이
class Solution {
private int index = 0;
public int[][] solution(int n) {
int[][] answer = new int[(int) (Math.pow(2,n)-1)][2];
move(n, 1, 3, 2, answer);
return answer;
}
public void move(int n, int start, int end, int between, int[][] answer) {
if (n == 1) {
answer[index++] = new int[]{start, end};
return;
}
move(n - 1, start, between, end, answer);
answer[index++] = new int[]{start, end};
move(n - 1, between, end, start, answer);
}
}나는 연결리스트를 새로 정의한후 새로 생길때마다 그 크기에 제한을 받지 않게끔하려고 했다. 그러나 연결리스트를 또다시 이차원배열로 정의하는 과정이 귀찮았다. 다른 사람의 풀이처럼 아예 얼만큼의 answer가 채워질 것인지를 구상해서 이차원배열의 크기를 정하고 재귀를 짜면 훨씬 간단했을 것 같다.
