99클럽 코테 스터디 7일차 TIL 하노이의 탑

📝 문제

프로그래머스

🔥 시도해본 접근 방식

처음에는 큰 원판이 작은 원판 위에 있어서는 안됩니다.라는 제약사항을 보지 못하고 쉬운 문제로 착각하여 풀었는데

첫 번째 답안을 제출하고 나서 전부 실패하는것을 보고 내가 문제를 잘못 파악했다는 것을 깨달았다.

많은 시간을 고민하였으나 나는 이 다음 문제를 어떻게 접근해야하는지 떠올리지 못하였다.

import java.util.*;

public class Solution {
    public int[][] solution(int n) {
        // 1, 2 ,3 번 기둥이 될 Stack 선언
        Stack<Integer> firstPole = new Stack<>();
        Stack<Integer> secondPole = new Stack<>();
        Stack<Integer> thirdPole = new Stack<>();

        // 기둥에 원판 셋팅, 기둥이 비어있을 때는 모든 원판이 들어갈 수 있으므로,
        // 원활한 값 비교를 위해 임의로 n + 1 이 들어있다고 선언
        for (int i = ++n; i > 0; i--) {
            firstPole.push(i);
        }
        secondPole.push(n);
        thirdPole.push(n);

        // 원판 옮김을 기록할 ArrayList 선언
        ArrayList<int[]> answerList = new ArrayList<>();

        do {
            if (firstPole.peek() < secondPole.peek()) {
                secondPole.push(firstPole.pop());
                answerList.add(new int[]{1, 2});
            } else if (firstPole.peek() > secondPole.peek()) {
                firstPole.push(secondPole.pop());
                answerList.add(new int[]{2, 1});
            } else if (thirdPole.peek() > firstPole.peek()) {
                thirdPole.push(firstPole.pop());
                answerList.add(new int[]{3, 1});
            } else if (thirdPole.peek() > secondPole.peek()) {
                thirdPole.push(secondPole.pop());
                answerList.add(new int[]{3, 2});
            }
        } while (thirdPole.size() < n); // 3번 기둥에 모든 원판이 꽃힐 때 까지 반복

        // 1, 2, 3, 4, 5

        // 리턴할 배열 선언
        int[][] answer = new int[answerList.size()][];

        // ArrayList를 배열로 변환
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }

        return answer;
    }
}

💦 풀이 실패

답지를 보고 다음과 같이 풀어보았다

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

    public List<int[]> hanoi(int n, int start, int end, int mid) {
        List<int[]> list = new ArrayList<>();

        if (n == 1) {
            list.add(new int[]{start, end});
        } else {
            // 1번 기둥의 n-1개를 3번을 걸쳐 2번으로 이동시킴
            list.addAll(hanoi(n - 1, start, mid, end));

            // 가장 큰 n을 1에서 3으로 이동시킴
            list.add(new int[]{start, end});

            // 2번의 기둥의 n-1개를 1번을 걸쳐 3번으로 이동시킴
            list.addAll(hanoi(n - 1, mid, end, start));
        }

        return list;
    }
}

 

 

문제를 보고 DFS인지 알아 차리는것이 가장 큰 관건인것 같지만 아직 훈련이 덜 된것 같다.

문제를 더욱 많이 풀어보고 감을 익혀야겠다.