99클럽 코테 스터디 7일차 TIL - [프로그래머스] 하노이의 탑(Java)

📌 오늘의 학습 키워드

[프로그래머스] 하노이의 탑 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/12946

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 1번 기둥에 있는 원판의 개수 n (1 ≤ n ≤ 15)
출력 : n개의 원판을 3번 원판으로 최소로 옮기는 방법의 2차원 배열

가능한 시간복잡도

O(2^n)

알고리즘 선택

스택

📌 코드 설계하기

1. 초기 상태를 스택에 푸시한다.
2. 스택에서 원소를 꺼내면서 3 ~ 4를 수행한다.
3. 원판이 하나일 때는 이동을 큐에 추가한다.
4. 원판이 여러 개일 때는 재귀적인 구조를 스택으로 표현한다.
5. 큐에서 이동을 하나씩 꺼내 결과 리스트에 추가한다.
6. 최종 결과를 2차원 배열로 변환해 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

queue.poll() : 큐의 첫 번째 요소를 삭제 및 반환한다

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    public int[][] solution(int n) {
        List<int[]> answer = new ArrayList<>();
        Stack<int[]> stack = new Stack<>();
        Queue<int[]> queue = new LinkedList<>();

        stack.push(new int[]{n, 1, 3, 2}); // 초기 상태

        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int disks = current[0];
            int from = current[1];
            int to = current[2];
            int aux = current[3];

            if (disks == 1) {
                queue.add(new int[]{from, to});
            } else {
                stack.push(new int[]{disks - 1, aux, to, from});
                stack.push(new int[]{1, from, to, aux});
                stack.push(new int[]{disks - 1, from, aux, to});
            }
        }

        while (!queue.isEmpty()) {
            answer.add(queue.poll());
        }

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