Leetcode | medium / 46.Permutations

1. 문제 분석

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
본 문제는 주어진 정수 배열인 nums를 가능한 모든 순열로 만들어서 반환하는 문제다. 어떠한 순서로든 반환이 가능하다. 
 

2. 로직 플로우

int 배열인 nums를 입력받고, 배열의 순서를 바꿀 때 사용할 temp 배열을 같은 int 배열로 생성한다. 그리고 dfs에서 방문 순서에 쓰일 visited 배열을 초기화 한 뒤, dfs 함수를 호출한다. 재귀함수 형태로 dfs를 통과할 때는 visited의 방문 체크를 true, false로 바꾸면서 진행한다. dfs를 재귀적으로 호출하기 전에 nums 배열의 i번째 값을 temp의 depth번째에 할당한다. 이 과정을 depth가 증가하여 nums 배열의 길이가 될 때까지 반복한다. depth가 nums 길이가 되면, 이때 temp에 담은 값들을 tempList에 담고, tempList에 담은 객체는 문제의 결과로 반환할 result에 담는다. 
2-1) 로직상세
1) nums를 입력받고, 반환할 배열인 result, 방문 여부를 체크할 boolean 배열인 visited를 초기화한다.
2) 인덱스 교환 시 사용할 배열인  temp를 생성하여 dfs 함수 호출 시 매개변수로 보낸다.
3) 인덱스 방문을 체크하기 위해 visited 배열에 true/false를 할당한다. boolean 할당은 재귀 호출을 기준으로 나눠서 추가한다. temp 임시 변수에는 depth를 index로 삼아서 i번째 값을 할당받도록 한다. 이는 배열의 순서를 바꾸는 로직에 해당한다. 
4) depth를 증가시키면서 재귀호출을 반복
5) depth가 nums.length가 되는 경우, 배열의 순서가 정렬된 형태로 할당되는 것을 반복했기 때문에 최종적으로 출력되는 형태는 정렬된 형태로 출력된다.
6) result 배열에 할당하여 모든 탐색을 마치면 그 배열을 반환한다.
 

3. 구현

import java.util.*;
class Solution {
    public List<List<Integer>> result;
    public boolean[] visited;

    public void dfs(int depth, int[] nums, int[] temp){
        if(depth == nums.length){
            List<Integer> tempList = new ArrayList<>();
            for(int i:temp){
                tempList.add(i);
            }
            result.add(tempList);
            return;
        }

        for(int i=0; i<nums.length; i++){
            if(!visited[i]){
                visited[i] = true;
                temp[depth] = nums[i];
                dfs(depth + 1, nums, temp);
                visited[i] = false;
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();
        visited = new boolean[nums.length];
        int[] temp = new int[nums.length];
        dfs(0, nums, temp);
        return result;
    }
}

 

4. 링크

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

Permutations - LeetCode

한 번 풀어보시면 이해가 잘 될 거라고 생각합니다. 문제 풀이와 관련해서 오류가 있으면, 아래에 댓글로 남겨주세요. 감사합니다 :)