[Grind75-LeetCode] Permutations JAVA

반응형

728x90

[Grind75-LeetCode] Permutations - Medium 

---

접근

• dfs

---

풀이

주어지는 배열로 만들 수 있는 모든 숫자 조합을 반환하는 문제이다. 더 자세히 말하면 조합이라기보다 배열의 원소들을 재배열해서 만들 수 있는 순서쌍을 모두 구하는 것이 맞는 것 같다. 배열이 [1, 2, 3] 일 경우 [1], [1, 2]와 같은 조합을 구하는 것이 아니라 [1, 2, 3], [1, 3, 2]처럼 모든 요소를 사용한 조합이기 때문에 재배열할 수 있는 경우의 수를 모두 반환하는 것이다. 

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums, new ArrayList<>(), result);

        return result;
    }

이번 문제도 dfs를 통해 진행하게 되고 원래 코드는 미리 리스트를 생성해 dfs 파라미터로 넘겨줬는데 메서드 실행 시 파라미터에서 생성하는 것과 1ms의 실행 시간 차이가 나 파라미터에서 바로 생성하는 코드로 가져왔다.

    private void dfs(int[] nums, List<Integer> ls, List<List<Integer>> res) {
        if (ls.size() == nums.length) {
            res.add(new ArrayList<>(ls));
        } else {
            for (int num : nums) {
                if (ls.contains(num)) continue;
                ls.add(num);
                dfs(nums, ls, res);
                ls.remove(ls.size() - 1);
            }
        }
    }

dfs 코드이다. 리스트의 크기가 3이 되면 재배열이 완료되어 결과 리스트에 추가해 준다. 그렇지 않다면 nums 배열을 순회하며 추가해 주는데 원소의 중복 없이 재배열해야 하므로 이미 리스트에 포함되어 있는 원소라면 건너뛴다. 포함되어 있지 않다면 리스트에 추가하고 다음 단계를 실행한 뒤 다시 마지막 원소를 제거해 주어 다른 방향으로 탐색을 할 수 있게 해 준다. 

1ms

---

0ms - 순서 변경

0ms의 코드는 약간 다른 방법으로 풀렸다. 대부분 dfs를 사용해 원소를 하나씩 추가하는 방향의 코드였는데 0ms 코드의 경우 원소 하나씩 추가하는 것이 아닌 배열 자체의 순서를 바꾼 뒤 배열을 통째로 결과 리스트에 추가하는 방법으로 진행되었다. 구현해야 하는 메인 메서드는 동일하기에 다른 부분만 보자

    private void backtrack(List<List<Integer>> result, int[] nums, int start) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(result, nums, start + 1);
            swap(nums, start, i);
        }
    }
    private void swap(int[] nums, int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

우선 start가 nums의 길이와 같으면 배열을 추가하게 되는데 start가 nums의 길이와 같다는 것은 모든 요소에 대한 반복이 끝나 for문이 종료되었다는 뜻으로 새로운 순서의 배열이 만들어졌다는 뜻이다. 그렇기 때문에 해당 배열을 그대로 결과 리스트에 추가해 준다. 그리고 nums를 순회하며 swap을 사용해 위치를 바꿔 주는데 배열 자체의 위치를 바꾸는 방법을 사용하기 때문에 같은 배열을 기반으로 여러 가지 조합을 완성할 수 있다. 

---

전체 코드

DFS - 1ms

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

        return result;
    }

    private void dfs(int[] nums, List<Integer> ls, List<List<Integer>> res) {
        if (ls.size() == nums.length) {
            res.add(new ArrayList<>(ls));
        } else {
            for (int num : nums) {
                if (ls.contains(num)) continue;
                ls.add(num);
                dfs(nums, ls, res);
                ls.remove(ls.size() - 1);
            }
        }
    }
}

 

0ms

import java.util.ArrayList;
import java.util.List;
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result,nums, 0);
        return result;
    }
    private void backtrack(List<List<Integer>> result, int[] nums, int start) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(result, nums, start + 1);
            swap(nums, start, i);
        }
    }
    private void swap(int[] nums, int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = sol.permute(nums);
        System.out.println(permutations);
    }
}