문제

programmers 하노이의 탑 문제 보러가기



문제점 해결

해당 문제는 재귀를 사용한 문제로, 탑이 2, 3, 4개 일때의 경로를 직접 써본 후 규칙을 찾아 코딩해봤지만 시간초과가 발생했다. 도저히 풀이방법이 떠오르지 않아서 다른 분의 블로그에 올라온 풀이 방법을 참고해 풀 수 있었다.

참고 블로그



풀이

import java.util.*;

class Solution {
	static List<int[]> result;

	public int[][] solution(int n) {
		result = new ArrayList<>();

		hanoi(n, 1, 3, 2);

		int[][] answer = new int[result.size()][2];

		for (int i = 0; i < result.size(); i++) {
			int[] arr = result.get(i);
			answer[i][0] = arr[0];
			answer[i][1] = arr[1];
		}

		return answer;
	}

	static void hanoi(int n, int st, int end, int mid) {
		int[] move = { st, end };

		if (n == 1) {
			result.add(move);
		} else {
			hanoi(n - 1, st, mid, end);
			result.add(move);
			hanoi(n - 1, mid, end, st);
		}
	}
}