(Java) 프로그래머스 - 하노이의 탑

처음에 문제의 2번째 조건을 읽지않아서 스택으로 풀면 되겠다고 생각하여 풀었다.

그런데 테스트 케이스 이외에는 다 틀렸다...  만약 두번째 조건이 없었다면 간단한 문제였을것이다.

성공 코드는 재귀를 이용해서 풀었다.

코드 자체는 간단하지만 은근히 생각할게 많았던 문제였다.

 

2번째 조건이 있으므로 1번 기둥에서 3번 기둥으로 바로 이동하지 못한다.

2번 기둥을 경유해서 가야 하는데 2번 기둥으로 가기 위해서는 3번 기둥을 먼저 이용해야 한다. 그리고 2번 기둥에서 3번 기둥으로 이동할때 1번 기둥을 이용해야 한다.

 

---

실패 코드

import java.util.*;
class Solution {
    public int[][] solution(int n) {
                List<int[]> list = new ArrayList<>();
        Stack<Integer> f = new Stack<>();
        Stack<Integer> s = new Stack<>();
        Stack<Integer> t = new Stack<>();

        for (int i = n; i > 0; i--) {
            f.add(i);
        }

        while (!(f.isEmpty())) {
            if (f.size() == 1) {
                t.push(f.pop());
                list.add(new int[]{1, 3});
            } else {
                s.push(f.pop());
                list.add(new int[]{1, 2});
            }
        }

        while (!(s.isEmpty())) {
            if (s.size() > 0) {
                t.push(s.pop());
                list.add(new int[]{2, 3});
            }
        }

        int[][] answer = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            int[] temp = list.get(i);
            answer[i][0] = temp[0];
            answer[i][1] = temp[1];
        }

        return answer;
    }
}

 

 

최종 코드

import java.util.*;
class Solution {
    static List<int[]> list;
    public int[][] solution(int n) {
        list = new ArrayList<>();

        // 재귀 호출
        recursion(1, 2, 3, n);

        // 배열 출력
        int[][] answer = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            int[] temp = list.get(i);
            answer[i][0] = temp[0];
            answer[i][1] = temp[1];
        }
        return answer;
    }
    static void recursion(int start, int via, int end, int n) {
        if (n == 1) {
            list.add(new int[]{start, end});
            return;
        }
        // 1번 기둥에서 3번 기둥을 거쳐 2번 기둥으로
        recursion(start, end, via, n - 1);
        list.add(new int[]{start, end});
        // 2번 기둥에서 1번 기둥을 거쳐 3번 기둥으로
        recursion(via, start, end, n - 1);
    }
}