[Leetcode] 15. 3Sum

Identifying the Problem

주어진 수열에서 세 숫자의 합이 0이 되는 경우를 찾아 해당 경우를 배열로 리턴한다.

단, 중복되는 경우는 제외한다.

Organizing thoughts

O(n³)으로 모든 경우를 찾는 방법도 있지만 비효율적이다.

 

MAIN IDEA는 오름차순정렬 후 탐색 값을 고정하고,

그 다음값과 맨 끝값을 가운데로 조여가면서 세 수의 합이 0인 경우를 찾는다.

정렬 전	-1	0	1	2	-1	-4
정렬 후	-4	-1	-1	0	1	2

위와 같을 때 탐색 값이 -4일 때 왼쪽을 탐색 값의 다음 값인 -1 오른쪽을 맨 끝 값인 2로 설정한다.

만약 세 수의 합이 0보다 크다면, 합을 줄여야 하므로 오른쪽 index를 줄인다.

만약 세 수의 합이 0보다 작다면, 합을 늘려야 하므로 왼쪽 index를 늘린다.

만약 세 수의 합이 0과 같다면, 정답 배열에 입력한다.

 

여기까지는 완벽하다.

그렇다면, 중복이 되는 조건은 어떻게 처리해야 할까?

 

중복이 되는 경우는 크게 두가지가 있다.

 

첫째는 합이 0일 때, left와 left의 다음 값이 같거나, right 와 right 이전 값이 같은 경우가 있다.

이는 각각의 이전 혹은 다음값과 다를 때까지 가운데로 index를 옮겨주면 된다.

 

둘째는 탐색하는 index가 이전과 같은 경우이다.

예를 들어 위의 배열에서 탐색 값이 nums[1] 일 때와 nums[2] 때 [-1,0,1] 이 정답 배열에 두번 생긴다.

이 같은 경우는 nums[2]일 때, 합을 구하는 과정을 생략하면 된다.

Sourcecode

#include<stdlib.h>

int compare(const void *one,const void *two){
	if(*(int *)one>*(int *)two)
		return 1;
	else if(*(int *)one<*(int*)two)
		return -1;
	else return 0;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){

    qsort(nums, numsSize, sizeof(int), compare); //오름차순 정렬
    
    int** ans = malloc(sizeof(int) * (numsSize) * (numsSize)); //정답 배열
    *returnSize = 0;
    int left, right, sum;
      
    for(int i=0; i<numsSize-2; i++)
    {

        left = i+1;
        right = numsSize - 1;
        
        if(i>0 && nums[i] == nums[i-1]) continue; 
        //탐색값이 이전과 같으면, 합 구하는 과정 생략
        
        
        while(left < right)
        {
            sum = nums[i] + nums[left] + nums[right];
            
            if(sum >0) right--;
            else if(sum<0) left++;
            else
            {
                ans[*returnSize] = malloc(sizeof(int) * 3); //정답배열에 추가
                
                ans[*returnSize][0] = nums[i]; 
                ans[*returnSize][1] = nums[left];
                ans[*returnSize][2] = nums[right];
                
                right--; left++;
                
                while(left < right && nums[right] == nums[right+1]) right--;
                while(left < right && nums[left] == nums[left-1]) left++;    
                //0인 경우 중복되는 경우 없애기
                
                (*returnSize)++;
            }   
        }
    }
    
    *returnColumnSizes = (int*)malloc(sizeof(int)*(*returnSize));
    for (int i = 0; i < *returnSize; i++)
        (*returnColumnSizes)[i] = 3;
    
    return ans;
}

Mistake

42번, 43번줄에서 left < right 를 해주지 않게 되면, left나 right가 지정된 메모리 범위를 벗어나는 경우가 생긴다.