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

1. 상태

: from: 원판이 현재 위치한 기둥

to: 원판이 이동해야 하는 기둥

n: 옮기려는 원판의 개수

 

2. 종료 조건

: 옮기려는 원판의 개수가 1개만 남은 경우

-> 이것이 가장 작은 부분 문제

 

3. 점화식

: 1) n-1개까지의 원판을 3번이 아닌 빈 기둥 2번으로 모두 옮긴다

2) 남은 원판 1개를 3번 기둥으로 옮긴다

3) 2번 기둥의 n-1개의 원판을 모두 3번으로 옮긴다

empty=6-from-to //2번 기둥
(n,from,to) = (n-1,from,empty) + (1,from,to) + (n-1,empty,to)

 

 

코드

import java.util.ArrayList;
import java.util.List;

public class 하노이_탑 {
    private List<int[]> hanoi(int n, int from, int to) { //이동과정을 담기 위해 배열을 담을 수 있는 List타입 반환
        if (n == 1) return List.of(new int[] {from, to}); //종료조건: 남은 1개의 원판을 from->to

        int empty = 6 - from - to; //2번 기둥

        List<int[]> result = new ArrayList<>();
        result.addAll(hanoi(n - 1, from, empty));
        result.addAll(hanoi(1, from, to));
        result.addAll(hanoi(n - 1, empty, to));
        return result;
    }

    public int[][] solution(int n) {
        return hanoi(n, 1, 3).toArray(new int[1][]); //행의크기가 1인 배열로 생성 후 리턴
    }
}

 

1. List.of(new int [] {from, to})
: 배열을 리스트로 변환하는 메서드

• 리턴되는 List는 불변-> add, remove 등 메서드 사용 불가
• Null값이 들어오면 에러 발생

* asList() 메서드는 변경메서드는 사용 가능

	Array.asList	List.of
삽입 (add)	불가능	불가능
삭제 (remove)	불가능	불가능
변경 (set, replace)	가능	불가능

 

 

 

2. ArrayList.addAll(Collection c)
: 인자로 전달되는 컬렉션 객체의 모든 아이템을 리스트에 추가
ArrayList.addAll(int index, Collection c)
: 전달받은 인덱스부터 컬렉션의 모든 아이템을 리스트에 추가

 

 

---

최적화된 코드

 

위의 코드는 재귀호출을 할 때마다 리스트를 새로 만들고 이어 붙이므로 비효율적이다.

따라서 인자로 리스트를 전달하도록 구현하여 하나의 List에 기록한다.

 

import java.util.ArrayList;
import java.util.List;

public class 하노이_탑 {
    private void hanoi(int n, int from, int to,List<int[]> list) { //이동과정을 담기 위해 배열을 담을 수 있는 List타입 반환
        if (n == 1) {
            list.add(new int[]{from, to}); //종료조건: 남은 1개의 원판을 from->to
            return;
        }

        int empty = 6 - from - to; //2번 기둥
        
        hanoi(n - 1, from, empty,list);
        hanoi(1, from, to,list);
        hanoi(n - 1, empty, to,list);
    }

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

        List<int[]> result = new ArrayList<>();
        hanoi(n,1,3,result);
        return result.toArray(new int[1][]); //행의 크기가 1인 배열로 생성 후 리턴
    }
}