[LeetCode] 15. 3Sum - 정렬(Sort) + 투포인터(Two Pointer) + 아이디어(Idea) JAVA

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

코드설명

정렬(Sort) + 투포인터(Two Pointer) + 아이디어(Idea) 를 활용합니다.

완전탐색으로도 가능합니다만, 재귀가 아닌 for문을 사용해야 성공합니다.

 

코드

시간초과 발생코드입니다. 3^2 x 10^6 이어서 1억을 초과하지 않기에 시간초과를 회필할 수 있을 것이라 생각했는데, 아쉽게 시간초과가 발생합니다.

(확인해보니, 저의 경우 재귀를 활용해서 작업을 했기에 시간초과가 납니다. 이중 for문으로 2개의 숫자를 정하고 3개의 숫자는 안하는 방식으로 하면 시간초과가 안납니다.)

import java.util.*;
class Solution {
    //Brute Force Complexity : 3^3 x 10^9
    //-> Better Brute Force : 3^2 x 10^6
    List<List<Integer>> arr = new ArrayList<List<Integer>>();
    HashMap<Integer, Integer> hashmap = new HashMap<>();
    HashSet<String> hashset = new HashSet<String>();
    public List<List<Integer>> threeSum(int[] nums) {
        for(int i=0; i<nums.length; i++){
            hashmap.put(nums[i], hashmap.getOrDefault(nums[i], 0) + 1);
        }
        
        // Arrays.sort(nums, 0, nums.length);
        DFS(nums, 0, 0, 0, new ArrayList<Integer>());

        return arr;
    }

    void DFS(int[] nums, int level, int idx, int sum, List<Integer> list){
        if(level == 2){
            //전체 중복체크.. 숫자는 3000까지 존재.
            //HashSet으로 한다면, 문자열을 가지고 있어야 한다.

            if(hashmap.containsKey(-sum) == true && hashmap.get(-sum) > 0){
                list.add(-sum);
                // String numString1 = "";
                String numString1 = String.valueOf(list.get(0)) + String.valueOf(list.get(1)) + String.valueOf(list.get(2));
                String numString2 = String.valueOf(list.get(0)) + String.valueOf(list.get(2)) + String.valueOf(list.get(1));
                String numString3 = String.valueOf(list.get(1)) + String.valueOf(list.get(0)) + String.valueOf(list.get(2));
                String numString4 = String.valueOf(list.get(1)) + String.valueOf(list.get(2)) + String.valueOf(list.get(0));
                String numString5 = String.valueOf(list.get(2)) + String.valueOf(list.get(0)) + String.valueOf(list.get(1));
                String numString6 = String.valueOf(list.get(2)) + String.valueOf(list.get(1)) + String.valueOf(list.get(0));

                if(hashset.contains(numString1) == false){
                    hashset.add(numString1);
                    hashset.add(numString2);
                    hashset.add(numString3);
                    hashset.add(numString4);
                    hashset.add(numString5);
                    hashset.add(numString6);
                    arr.add(new ArrayList<Integer>());
                    arr.get(arr.size() - 1).add(list.get(0));
                    arr.get(arr.size() - 1).add(list.get(1));
                    arr.get(arr.size() - 1).add(list.get(2));
                }
                list.remove(list.size() - 1);
            }

            return ;
        }

        for(int i=idx; i<nums.length; i++){
            list.add(nums[i]);
            hashmap.put(nums[i], hashmap.get(nums[i]) - 1);
            DFS(nums, level + 1, i + 1, sum + nums[i], list);
            hashmap.put(nums[i], hashmap.get(nums[i]) + 1);
            list.remove(list.size() - 1);
        }

    }
}

 

투포인터를 활용한 신박한 방식입니다.

가장 핵심은, 중복된 숫자가 연속될 경우 중복 연산을 애초에 피할 수 있다는 것 입니다. 중복될 경우에는 i의 경우는 아예 다시는 판단하지 않고, j의 경우에는 계속해서 넘어가도록 처리합니다. ( 생각해보면, i값을 기준으로 숫자들이 연속된다면, 의미가 없음을 알 수 있습니다. j값을 기준으로 해도 마찬가지입니다. )

import java.util.*;

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        Arrays.sort(nums);

        for(int i=0; i<nums.length; i++){
            if(i > 0 && nums[i] == nums[i-1]){
              	// i++; continue 대신 이걸로 처리할시 중복이 연속될경우를 처리못합니다. 
                continue;
            }

            int j = i + 1;
            int k = nums.length - 1;

            while( j < k){
                int total = nums[i] + nums[j] + nums[k];
                if(total > 0){
                    k -= 1;
                }else if(total < 0){
                    j += 1;
                }
                else {
                    answer.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j += 1;

                    //while(l2 < r1){ 처음에 잘못작성한 코드입니다. 이렇게 되면 무한루프가 걸립니다.
                    // while문 자체에 nums[l2-1] == nums[l2] 일때만 이동하도록 처리해야만 이동합니다.
                    //    if(nums[l2 - 1] == nums[l2]){
                    //        l2 += 1;
                    //    }
                    //}
                    
                    while(nums[j-1] == nums[j] && j < k){ 
                        j += 1;
                    }
                    
                }
            }
        }
        return answer;
    }
}