[자바 알고리즘 인터뷰] 12장 그래프 (3) 순열

https://leetcode.com/problems/permutations/description/

- 서로 다른 정수를 입력받아 가능한 모든 순열(Permutation)을 리턴하라 

 

 

풀이 1) DFS를 활용한 순열 생성

 

- 순열이란 결국 모든 가능한 경우를 그래프 형태로 나열한 결과라고 할 수 있기 때문에 그래프로 표현해보면 다음과 같다. 

출처: 자바 알고리즘 인터뷰 with 코틀린 저자:박상길 <책만>

 

- 리프 노드(Leaf), 즉 A3의 모든 노드가 순열의 최종 결과이다.

- 레벨이 증가할수록 자식 노드의 개수가 점점 적어진다. A0의 자식 노드는 3개였다가 A1의 자식 노드는 2개, A2의 자식 노드는 1개 순으로, 이는 순열의 수식이기도 한 3*2*1 형태이기도 하다. 

 

 public void dfs(List<List<Integer>> results, List<Integer> prevElements,List<Integer>elements)
    {
        //리프 노드에 도달하면 결과에 추가
        if(elements.isEmpty()) {
            //prevElements의 내용을 결과에 삽입
            results.add(prevElements.stream().collect(Collectors.toList()));
        }

        //전달 받은 엘리먼트를 모두 탐색
        for(Integer e : elements)
        {
            //전달받은 엘리먼트에서 현재 엘리먼트를 제외하고 nextElements를 새롭게 구성
            List<Integer> nextElements = new ArrayList<>(elements);
            nextElements.remove(e);

            //prevElements는 기존 값에 현재 엘리먼트 추가
            prevElements.add(e);
            //재귀 dfs
            dfs(results,prevElements,nextElements);
            //돌아온 이후에는 prevElements에서 현재 엘리먼트 삭제
            prevElements.remove(e);
        }
    }

 

 

- 이전 값을 prevElements 변수에 하나씩 덧붙여 가며 계속 재귀 호출을 진행한다.

- 현재 엘리먼트는 제외하고 nextElements를 만드는데, 이렇게 되면 자식 노드의 개수가 4개,3개,,..1개 순으로 점점 줄어들 것이다. 

- 리프 노드에 도달한 경우, 즉 더이상 남아있는 엘리먼트가 없는 경우 결과에 하나씩 담는다. 

 

 

 

class Solution {
    public void dfs(List<List<Integer>> results, List<Integer> prevElements,List<Integer>elements)
    {
        //리프 노드에 도달하면 결과에 추가
        if(elements.isEmpty()) {
            //prevElements의 내용을 결과에 삽입
            results.add(prevElements.stream().collect(Collectors.toList()));
        }

        //전달 받은 엘리먼트를 모두 탐색
        for(Integer e : elements)
        {
            //전달받은 엘리먼트에서 현재 엘리먼트를 제외하고 nextElements를 새롭게 구성
            List<Integer> nextElements = new ArrayList<>(elements);
            nextElements.remove(e);

            //prevElements는 기존 값에 현재 엘리먼트 추가
            prevElements.add(e);
            //재귀 dfs
            dfs(results,prevElements,nextElements);
            //돌아온 이후에는 prevElements에서 현재 엘리먼트 삭제
            prevElements.remove(e);
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        //결과 저장 리스트 선언
        List<List<Integer>> results = new ArrayList<>();
        //int[]를 List<Integer>로 변경
        List<Integer> lst = Arrays.stream(nums).boxed().collect(Collectors.toList());
        //dfs 시작
        dfs(results,new ArrayList<>(),lst);

        return results;
    }
}

5밀리초