문제

LeetCode - Permutation

Code

1차 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> numsList = Arrays.stream(nums).boxed().collect(Collectors.toList());
        searchDFS(numsList, new ArrayList<>(), result);
        return result;
    }

    public void searchDFS(List<Integer> nums, List<Integer> path, List<List<Integer>> result) {
        if (nums.size() == 0) {
            result.add(path);
            return;
        }

        for (int num : nums) {
            List<Integer> newNums = nums.stream().filter(ele -> ele != num).collect(Collectors.toList());
            List<Integer> newPath = new ArrayList<>(path);
            newPath.add(num);
            searchDFS(newNums, newPath, result);
        }
    }
}

• DFS를 이용하여 풀이하였다.
• 현재의 숫자를 제외하여 새로운 newNum을 만들어서 넘기고, 현재의 결과 값 또한 새로운 인스턴스로 만들어서 넘겼다.
• 매 탐색마다 새로운 인스턴스를 만들면서 시간도 오래 걸리고 메모리도 많이 잡아 먹는다.
  

2차 풀이

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

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        searchDFS(nums, new ArrayList<>(), result);
        return result;
    }

    public void searchDFS(int[] nums, List<Integer> path, List<List<Integer>> result) {
        if (nums.length == path.size()){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int num: nums){
            if (!path.contains(num)){
                path.add(num);
                searchDFS(nums, path, result);
                path.remove(path.size() - 1);
            }
        }
    }
}

• num에 대해 새로운 인스턴스를 만들지 않고, 현재 path에 포함이 되어 있는지 확인하는 것으로 대체한 풀이이다.

Reference

[Leetcode][Java] 46 Permutations (순열)