알고리즘

[LeetCode] 3Sum - 이분탐색, 투포인터

제이G 2023. 4. 14. 18:17

리뷰

해당 문제는 완전탐색 → 완전탐색 조합 → 이분탐색으로 이어지기까지 시간복잡도를 어떻게 단축시킬 수 있는지, 접근 방법에 대해 생각해본 좋은 문제였다.

1. 조합을 구하는 시간복잡도가 너무 크면 가지치기가 큰 의미가 없을 수 있다.

완전탐색으로 조합을 모두 구하는 경우는 O(3000 C 3)으로 TLE가 발생한다. 하지만, 다른 풀이가 생각나지 않았고 promising (유망함)으로 가지치기를 시도하였으나 TLE가 발생하였다. 이럴 경우, 시간 복잡도를 만족하는 다른 풀이를 생각해보자.

 

2. 시간복잡도를 줄여나가는 과정: 시간복잡도를 쪼개고 어느 부분의 시간을 단축시킬 수 있을지 고민하자.

시간복잡도를 줄여나가기 위해선 처음에 완전탐색부터 시작할 것이다. 완탐의 시간복잡도에서 정확히 어느 부분의 계산에서 시간복잡도를 줄일 수 있을지 파악하자.

예를 들어, 해당 문제는 완전탐색의 경우 O(N^3)의 시간이 소요된다. 이를 쪼개서 생각하면 O(N * N * N) (N: i구하는 시간, N: j구하는 시간, N: k구하는 시간) 이다. nums[i], nums[j]를 O(N^2)로 구해놨다면, nums[k]는 nums[i] + nums[j] + nums[k] == 0이라는 조건에 맞게, nums를 이분탐색하여 구할 수 있을 것이다. 즉, k구하는 시간을 log scale로 떨어트릴 수 있을 것이다.

 

3. 조건을 확실히 짚고 넘어가자.

조건1:  i != j, i != k, j != k

서로 다른 위치만 가능하고, for문 탐색할 때 i, j, k의 범위를 유의해야할 것이다.

 

 

조건2:  중복은 포함하지 않는다.

ex) (-1, 0, 1), (0, 1, -1)

이를 정확히 짚고 구현해줘야 한다.

 

 

 

이분탐색 풀이

 

[제한]

  • 숫자개수 n: 3 ~ 3,000
  • O(n^2)까지 가능

 

[유형]

Goal: nums[i] + nums[j] + nums[k] == 0인 모든 (nums[i], nums[j], nums[k])를 구하라.

* i != j, i != k, j != k  → 서로 다른 위치여야 함.

* 중복은 포함하지 않는다.  → (-1, 0, 1) , (0, 1, -1)

 

유형1. 완전탐색: O(N^3) → TLE

O(i 구하는 시간 * j 구하는 시간 * k 구하는 시간)

 

유형2. 완탐으로 조합구하기: O(3000 C 3) → O(45억) → TLE

 

유형3. 완탐에서 일부를 log scale로 떨어트릴 순 없을까?

완전탐색: O(N * N * N) (N: i구하는 시간, N: j구하는 시간, N: k구하는 시간) 

nums[i] 와 nums[j]를 O(N^2)로 구했다면, nums[i] + nums[j] + nums[k] == 0을 만족하는 nums[k]값이 nums에 존재하는지 확인하면 될 것. 정렬 후, 이분탐색

 

=> 정렬 + 이분탐색: O(N * N * logN) (N: i구하는 시간, N: j구하는 시간, N: k구하는 시간)

 

 

 

[설계]

1. nums 정렬

2. for문으로 i, j 탐색하며 k는 이분탐색

 

중복을 포함하지 않아야 하므로 다음과 같은 조건식 추가.

// 이미 이전 완탐에서 (i, x, x)를 구한경우 (정렬된 상태이므로)
private boolean alreadyFindOne(int i, int[] nums) {
	return i!=0 && nums[i-1]==nums[i];
}
// 이미 이전 완탐에서 (i, j, x)를 구한경우. (정렬된 상태이므로)
private boolean alreadyFindTwo(int i, int j, int[] nums) {
	return j!=i+1 && nums[j-1]==nums[j];
}

 

 

 

[코드]

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        return pro(nums);
    }
    //O(N^2 logN)
    private List<List<Integer>> pro(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        // 1. 정렬: O(N logN)
        sortByAscending(nums);
        // 2. for문 탐색하며 이분탐색: O(N * NlogN)
        for(int i=0; i<nums.length; i++) {
            if(alreadyFindOne(i, nums)) {
                continue;
            }
            for(int j=i+1; j<nums.length-1; j++) {
                if(alreadyFindTwo(i, j, nums)) {
                    continue;
                }
                int sum = nums[i] + nums[j];
                int k = 0 - sum;
                if(binarySearch(k, j+1, nums)) {
                    List<Integer> temp = List.of(nums[i], nums[j], k);
                    answer.add(temp);
                };
            }
        }
        return answer;
    }

    // 이미 이전 완탐에서 (i, x, x)를 구한경우 (정렬된 상태이므로)
    private boolean alreadyFindOne(int i, int[] nums) {
        return i!=0 && nums[i-1]==nums[i];
    }

    // 이미 이전 완탐에서 (i, j, x)를 구한경우. (정렬된 상태이므로)
    private boolean alreadyFindTwo(int i, int j, int[] nums) {
        return j!=i+1 && nums[j-1]==nums[j];
    }

    // find가 있으면 true, 없으면 false
    private boolean binarySearch(int find, int left, int[] nums) {
        int right = nums.length-1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == find) {
                return true;
            } else if(nums[mid] < find) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

    private void sortByAscending(int[] nums) {
        Arrays.sort(nums);
    }
}