코딩테스트 연습 - 하노이의 탑

문제 이해하기

• 한 기둥에 꽂힌 원판들을 “ 그 순서 그대로 “ 다른 기둥으로 옮겨 다시 쌓는 것.
• 원래 상태도 : 작은 원판이 위에 쌓여있는 상태임.
• 1번 기둥에만 원판들이 존재함

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어선 안 된다.

세 개의 기둥이 존재함.

1번에 있는 n 개의 원판 → 3번 원판으로 “최소 횟수"로 옮길 거임.

( 사실 몇 번에서 몇번으로 이동하는지는 중요하진 않음 )이라고 생각했는데 result 형태가 원판을 이동시킨 이동 과정이라서 중요하다. from → to 로 이동하고, 이동 할 때 마다, extra 기둥이 달라진다.

예를들어 1 → 2, 1→ 3, 2→ 3

[ [1,2], [1,3], [2,3] ]

문제 풀이

(1시간 30분.. )

3개의 기둥이 있는 하노이탑 문제 → “바닥에 있는 원반"을 뺄 수 있도록 만들어야 함. ( 규칙 상, 더 큰 원반이 위에 올 수는 없기 때문이다 )

• 따라서

  1. 1 ~ n-1 원판을 “다른 기둥" 에 옮겨두고

  2. → n 번 원판을 3번으로 이동

  3. → 다른 기둥에 있는 1~n-1 원판들도 3 번으로 이동하는 과정

     이 필요 하다.

• 단순히 최소 개수로만 생각하면 cache[n] 은 원판의 개수가 n 일 때, 이동 횟수 라고 할 수 있겠지만
• 지금 구해야 하는 것은 , 어떤 식으로 이동했는지에 대한 것임.

이 문제를 “재귀적"으로 풀려면 어떻게 해야할까?

// 대충 이런 식 
void hanoi(int n, int from, int extra, int to) { 
	int[] move = new int[] { from, to } ;
	
	hanoi( n - 1, from, extra ); // 1 ~ n 은 다른 기둥으로 옮겨두고
	answert.append(move);
	hanoi( n - 1, extra , to ) ; // 1 ~ n 은 이제 "다른기둥" -> to 기둥으로 옮긴다 
} 

import java.util.*;
class Solution {

	List<int[]> orders = new ArrayList<>(); // 여기에 int[2] 를 추가 해 나간다

	public int[][] solution(int n) {
		int[][] answer = {};

		hanoi(n, 1,2,3);

		answer = orders.toArray(new int[orders.size()][]);

		return answer;
	}

	// 1 ~ n 원판들을 기둥 from 으로부터 to 기둥으로 이동한다. 이 과정에서 나머지 기둥 extra 를 사용하게 되기에 이것도 전달해주어야함
	private void hanoi(int target, int from, int extra, int to) {
		int[] move = new int[]{from, to};

		if (target == 1) {
			orders.add(move);
			return;
		}
		// 1 ~ n-1 원판들은 일단 extra 로 이동해 줘야 한다
		hanoi(target-1, from, to, extra);
		// n 번 원판은 to 로 이동 해 준다
		orders.add(move);
		// 1 + n -1 원판들을 extra -> to 로 이동해 준다
		hanoi(target-1, extra, from, to);
	}
}

List of Array → Array of Array

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
}

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
}

@IntrinsicCandidate
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
				// 비어있는 객체를 생성하고 
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
				// original 에 있던 값들을 복사 한다
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }