[leetcode] Medium-15번. 3Sum 문제풀이

문제

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

 

 

 

문제풀이 (DFS 사용한 코드 실패: 시간초과)

package SITE03_leetcode.medium;

import java.util.*;

/**
 * https://leetcode.com/problems/3Sum/
 */
public class M009_leetCode15_3Sum_시간초과 {
    static List<List<Integer>> list = new ArrayList<>();
    static boolean[] visited;
    static int[] map;
    static int n;
    static int size;

    public static void main(String[] args) {
        M009_leetCode15_3Sum_시간초과 solution = new M009_leetCode15_3Sum_시간초과();

        System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        //System.out.println(solution.threeSum(new int[]{}));
        //System.out.println(solution.threeSum(new int[]{0}));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        map = nums;
        n = map.length;
        visited = new boolean[n];

        dfs(0);

        return list;
    }

    public static void dfs(int index) {
        /* sum = 0 일 경우 */
        if (size == 3) {
            List<Integer> local = new ArrayList<>();
            int sum = 0; /* 합계는 0 이여야 한다 */

            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    local.add(map[i]);
                    sum += map[i];
                }
            }

            if (sum == 0) {
                Collections.sort(local); // 오름차순 정렬

                if (!list.contains(local)) {
                    list.add(local);
                }
            }
        }

        for (int i = index; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                size++;

                dfs(i);

                visited[i] = false;
                size--;
            }
        }
    }
}

 

 

 

 

문제풀이 (정답)

package SITE03_leetcode.medium;

import java.util.*;
import java.util.stream.IntStream;

/**
 * https://leetcode.com/problems/integer-to-roman/
 */
public class M009_leetCode15_3Sum_풀이 {
    public static void main(String[] args) {
        M009_leetCode15_3Sum_풀이 solution = new M009_leetCode15_3Sum_풀이();

        System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        //System.out.println(solution.threeSum(new int[]{}));
        //System.out.println(solution.threeSum(new int[]{0}));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();

        if (nums.length == 1) {
            return new ArrayList<>();
        }

        // 정렬
        // 사실, Arrays.sort(nums) 로도 가능한데 stream 써봤다.
        int[] sorted = Arrays.stream(nums).sorted().toArray();

        for (int start = 0; start < sorted.length; start++) {
            int mid = start + 1;
            int end = nums.length - 1;

            while (mid < end) {
                if (sorted[start] + sorted[mid] + sorted[end] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(sorted[start]);
                    list.add(sorted[mid]);
                    list.add(sorted[end]);

                    Collections.sort(list); // 정렬
                    result.add(list);

                    end = end - 1;
                } else if (sorted[start] + sorted[mid] + sorted[end] < 0) {
                    mid = mid + 1;
                } else if (sorted[start] + sorted[mid] + sorted[end] > 0) {
                    end = end - 1;
                }
            }
        }


        return new ArrayList<>(result);
    }
}

 

매개변수 nums 배열을 오름차순으로 정렬한다. 그리고 총 3개의 포인트(start, mid, end) 로 둔다. 만약의 합이 0보다 작다면 min + 1 이 되어야 0에 가까워진다. 또한 합이 0보다 크다면 end - 1 을 해야 0에 가까워진다. 0에 가까워지기 위한 point 를 설정하고, 0이 되면 end - 1 을 실행하여 모든 자릿수를 체크하게한다.