프로그래머스 lv2 하노이의 탑

문제 링크

하노이의 탑

풀이

재귀를 푸는 방법은
1. 규칙을 구하고
2. 적용한다 이다.

하노이의 탑은 아래와 같은 규칙을 발견했다.

1. n 개의 원판중 n-1 개의 원판을 두 번째 기둥으로 옮기고
2. 마지막 원판을 세 번째 기둥으로 옮긴다음
3. n-1 개의 원판을 세번째로 옮긴다.

위 규칙을 토대로 코드를 작성하면 위와 같다.

import java.util.ArrayList;
import java.util.List;

class Solution {
	private  int[][] answer;
	private  List<int[]> list = new ArrayList<>();
    
	public int[][] solution(int n) {
		hanoi(n, 1, 2, 3);
		return list.toArray(new int[list.size()][]);
	}

	public void hanoi(int n, int from, int by, int to) {
		if ( n != 0 ) {
			hanoi(n - 1, from, to, by);
			list.add(new int[]{from, to});
			hanoi(n - 1, by, from, to);
		}
	}
}

소감

재귀는 규칙 발견하기전까지가 가장 괴롭다..