[프로그래머스/Level2] 하노이의 탑 (JAVA)

📖 문제

프로그래머스

 

 

 

 

💡  풀이 방식

• 재귀

필요 자료구조
- (시작점, 도착점) 값 저장용 리스트 List<int[]> ⭐
- 정답 출력용 2차원 int형 배열 answer

 

. 재귀 함수를 활용해 하노이의 탑을 구현한다.

Hanoi(이동할 원판 갯수, 시작점, 경유지, 도착지)

 

 1) (n - 1)개의 원판을 1번째 > 2번째 기둥으로 옮긴다. ▷ Hanoi(n - 1, 1, 3, 2)

 2) 남은 1개 원판을     1번째 > 3번째 기둥으로 옮긴다. 

 3) (n - 1)개의 원판을 2번째 > 3번째 기둥으로 옮긴다. ▷ Hanoi(n - 1, 2, 1, 3)

 

 

 

💥 유의사항

정답 출력용 2차원 int형 배열의 크기는 [배열 저장용 리스트의 크기][2]여야 한다.

여기서 그냥 n을 넣으면 시간초과 에러가 발생한다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static List<int[]> list = new ArrayList<>();
    
    public int[][] solution(int n) {  
        Hanoi(n, 1, 2, 3);
        
        // 리스트에 저장한 값들을 2차원 배열로 옮기기
        int[][] answer = new int[list.size()][2];   // 배열 크기 주의!
                
        for(int i = 0 ; i < list.size() ; i++) {
            int[] cmd = list.get(i);
            answer[i][0] = cmd[0];
            answer[i][1] = cmd[1];
        }
        
        return answer;
    }
    
    private static void Hanoi(int n, int from, int via, int to) {
        if(n == 1) {
            list.add(new int[] {from, to});
            return;
        }
 
        Hanoi(n - 1, from, to, via);        // 1) 원반 n-1개를 1→2로 이동
        list.add(new int[] {from, to});     // 2) 원반 1개를 1→3으로 이동
        Hanoi(n - 1, via, from, to);        // 3) 원반 n-1개를 2→3으로 이동
    }
}

 

 

 

➕ 다른 풀이 방식

- 배열을 저장한 리스트를 람다를 활용해 1줄로 표현하시다...

int[][] answer = list.stream().toArray(int[][]::new);

[JAVA/자바][프로그래머스 12946] 하노이의 탑

---

💦 어려웠던 점

- List<int[]>를 활용해 시작점과 도착점을 저장할 생각을 하지 못 했다. 그냥 2차원 배열 하나 더 만들어서 거기에 인덱스대로 값 저장해서 쓰려고 했는데 하나가 밀리고 입력이 제대로 안 되길래 다른 분 답 보고 해결하였다,,,

 

 

1회독	2회독	3회독	4회독	5회독
V	240707

 

 

(+240707 2회독)

- List<int[]>를 쓸 생각을 했다.

- 하노이의 탑 방법) 원판을 1>2, 1>3, 2>3 순서로 이동시킬 아이디어도 스스로 떠올렸다.

- 하노이 함수 인자로 남은 인자 갯수를 가져간다는 것을 빠뜨렸다.

import java.util.*;
 
class Solution {
    static List<int[]> list = new ArrayList<>();
    
    public int[][] solution(int n) {
        Hanoi(n, 1,2,3);
        
        int[][] answer = new int[list.size()][2];
        for(int i = 0 ; i < answer.length ; i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
    
    private static void Hanoi(int n, int from, int via, int to) {
         if(n == 1) {
             list.add(new int[]{from, to});
             return;
         }
        
         Hanoi(n-1, from, to, via);     // 1 → 2
         list.add(new int[]{from, to}); // 1 → 3
         Hanoi(n-1, via, from, to);     // 2 → 3
    }
}

---

(참고)

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

[백준/JAVA] 11729번: 하노이 탑 이동 순서