🟠[Leet code - 15] 3Sum ❌

3Sum - LeetCode

문제

• Input
  정수배열 nums
• Output
  서로 다른 인덱스를 가지고 있는, 합이 0인 원소 3개의 해집합들
  ※같은 값이어도 다른 인덱스라면 집합에 모두 포함이 가능하다.
• Constraints
  순서와 상관없이 원소의 값들이 모두 같은 해집합들은 하나로 간주한다.

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관없음 | O(log n) : 크게  상관없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

시간은 $3 \le n \le 3000$ 이므로, n^2부터 고려해볼 수 있다.

 

 

해결 계획(오답)

중복된 해집합을 하나로 묶는 게 좀 까다로운거 같다고 느껴서,
중복된 해집합을 순회하면서  자연스럽게 처리할 방법이 존재할 거 같다고 생각했다.

 

먼저 정렬을 해도 고유 인덱스를 반환해야하는 것은 아니니까 나쁘지 않을 것 같아서 정렬을 해보았고,

정렬된 상태에서 순회를 하는 시뮬레이션을 하며 각 원소에서 어떻게 처리돼야 정답이 나올까 생각했다.

그러다 탐색중인 원소가 해집합의 가운데 값이라면?이라는 아이디어가 생각나서,

자연스럽게 왼쪽과 오른쪽을 투 포인터로 탐색하여 하나씩 피킹 하는 아이디어까지 생각이 났다.

 

순회를 하는 값을 가운데 값이라고 생각할때, 가운데 값만 중복처리를 하면 자연스럽게 중복처리가 되는 것 같았기에 진행했고,

추가로 세 값의 합이 작으면 오른쪽 포인터를 움직이고, 크면 왼쪽 포인터를 움직이는 방식으로 진행하기로 했다.

 

아래와 같은 수도 코드를 작성했었다.

SORT(nums)

FOR 1 <= i < nums.size - 1
{
    // 중복처리하는거임
    IF (nums[i - 1] == nums[i] && i != 1) continue;
    
    WHILE(TRUE)
    {
        sum = left + center + right 
        sum이 0이면 저장.

        IF (sum이 0보다 작으면)
        {
            현재 right가 마지막이면 break
            아니면 right이동 
        }
        IF (sum이 0보다 크면)
        {
            현재 left 마지막이면 break
            아니면 left 이동 
        }
    }
}

 

 

되돌아보기

중앙 값 고정은 틀렸다

나는 nums[i]와 nums[i - 1]이 같으면 넘어가는 식으로 중앙값의 중복을 제거했었는데, 이는 크리티컬 한 예외가 존재했다.

 

nums = [-4, -1, -1, -1, 2] 라면 아래와 같이 진행된다.

• i = 1
  1번 인덱스를 중앙 값으로 계산하면 만족하는 해가 없다.
• i = 2
  이전 값인 -1과 같아 중복처리가 되어 넘어간다.
  하지만 i = 2일때 [-1, -1, 2]라는 해가 존재한다.

그러니까 중앙에 오는 값이 같아도 인덱스가 다르면 해의 여부가 달라지기 때문에, 모든 경우를 볼 수 없다는 뜻과 일맥상통한다.

그렇다고 중앙 값을 중복처리 하지 않는다? 그러면 개같이 중복이 되는 케이스에 걸려 불통과하게 된다.

 

그래서 중앙 값 고정으로는 문제를 풀 수 없게 된다.

 

어떻게 생각을 했었어야 했나

일단 예외를 찾지 못했었으니까 첫 번째로 예외를 찾았어야 했고, (이게 실패 원인이 제일 큼;)
두 번째로 그럼 중앙값 고정으로는 중복 처리를 할 수 없다는 걸 깨달았어야 했고,
세 번째로 다른 값을 고정해볼까? 까지 생각을 했었어야 하지 않았나 싶다.

 

왼쪽 값 고정

왼쪽 값을 고정하면 nums[i]와 nums[i - 1]이 같으면 넘어가는 식으로 중복을 제거해도 문제가 없었다.

중앙 값을 고정하면 불가능하다.

 

심지어 부가적으로 두 가지 장점이 있다.

• 1. while (l < r) 으로 인덱스 제한을 할 수 있어서 , l과 r의 범위 제한이 더 쉬워진다. 
• 2. 고정 된 왼쪽 값이 0을 초과할 때는 순회하는 값들이 정렬되어 있기 때문에 모두 양수이기에 탐색을 종료해도 된다.

 

 

구현

vector<vector<int>> threeSum(vector<int>& nums) 
{
    sort(nums.begin(), nums.end());

    vector<vector<int>> ret;
    for (int i = 0; i < nums.size(); ++i)
    {
    	if(0 < nums[i]) break;
        if(i != 0 && nums[i-1] == nums[i]) continue;

        int l = i + 1;
        int r = nums.size() - 1;


        while(l < r)
        {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) ret.push_back({nums[i], nums[l], nums[r]});

            if (sum <= 0) 
            {
                do{ ++l; }while(l < nums.size() && nums[l - 1] == nums[l]);
            }

            if (0 <= sum) 
            {
                do{ --r; }while(0 <= r && nums[r] == nums[r + 1]);
            }
        }
    }

    return ret;
}