7월 28일 99클럽 항해 7일차

99클럽 항해 6일차

 

오늘의 문제는 하노이의 탑이다.

안그래도 최근 자료구조 스택을 복습하면서 혼자 하노이의 탑 알고리즘을 공부해서 정말 쉽게 풀 수 있었다.

 

 

문제에서 주어지는 3개의 기둥에서 하노이의 탑을 출력하는 문제이다.

        ->하노이의 탑 점화식을 구현한다.

                -> 1번 기둥의 n-1개를 3번을 걸쳐 2번으로 이동시킴
                ->  가장 큰 n을 1에서 3으로 이동시킴
                ->  2번의 기둥의 n-1개를 1번을 걸쳐 3번으로 이동시킴

        -> arrayList를 배열로 생성해서 해당 배열을 하나씩 넣어 2차원 배열 answer에 입력한다.

순서로 문제를 해결하였다.

 

 

import java.util.*;

class Solution {
    private List<int[]> ansList;

    public int[][] solution(int n) {

        ansList = new ArrayList<>();
        game(n, 1,3, 2);

        int[][] answer = new int[ansList.size()][];
        for(int i=0; i<ansList.size(); i++){
            answer[i] = ansList.get(i);
        }
        return answer;
    }

    private void game(int n, int start, int end, int mid) {
        if(n == 1){
            ansList.add(new int[]{start, end});
            return;
        }
        game(n-1, start, mid, end);
        ansList.add(new int[]{start, end});
        game(n-1, mid, end, start);
    }
}