[LeetCode]세수의 합

Inhwan98·2023년 1월 17일

C PTUStudy algorithm leetcode 알고리즘

PTU STUDY_leetcode

목록 보기

9/24

문제

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라

예제

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

코드

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
  
	vector<vector<int>> result;
	set<vector<int>> set_temp;

	vector<int>::iterator current = nums.begin();
	vector<int>::iterator left;
	vector<int>::iterator right;

	int sum = 0;
	int Column = 0;
	sort(nums.begin(), nums.end());

	while (current < nums.end() - 2)
	{
		left = current + 1;
		right = nums.end() - 1;

		while (left < right)
		{
			sum = *(current)+*(left)+*(right);
			if (sum < 0) left++;
			else if (sum > 0) right--;
			else
			{
				set_temp.insert({ *(current) , *(left) , *(right) });
			    left++;
				right--;
			}
		}
		current++;
	}

	copy(set_temp.begin(), set_temp.end(),
		back_inserter(result));
        
        return result;
      }

};

풀이

1.

sort(nums.begin(), nums.end());

오름차순으로 정렬하여 투 포인터 방식을 이용한다.

2.

	//1.
	while (current < nums.end() - 2)
	{
    	//2.
		left = current + 1;
		right = nums.end() - 1;
		
		while (left < right)
		{
        	//3.
			sum = *(current)+*(left)+*(right);
			if (sum < 0) left++;
			else if (sum > 0) right--;
			else
			{
            	//4.
				set_temp.insert({ *(current) , *(left) , *(right) });
			    left++;
				right--;
			}
		}
        //5.
		current++;
	}

반복자 current를 제일 좌측에서 시작으로 left, right를 포함한 총 3개씩 계산하기 때문에, current가 마지막 인덱스의 전 인덱스에 도착하게 된다면 3개씩 계산 할 수 없기 때문에 nums.end() - 2 에 current가 도달하게 되면 반복문을 종료한다.
left는 무조건 current의 다음에서 시작하고, right는 마지막 반복자에서 시작한다.
sort로 인해 nums의 배열은 오름차순으로 정리 되어있다. 따라서 current, left, right의 반복자 3개의 값을 더 했을때, sum이 0보다 크다면 right 반복자를 왼쪽으로 이동해서 값을 줄여주고, sum이 0보다 작다면 elft 반복자를 오른쪽으로 이동해서 값을 키워준다.
만약 sum이 0과 같아진다면, set컨테이너인 set_temp에 current, left, right의 값을 넣어 준다. 중복된 값을 없애주기 위해 set 컨테이너를 사용하였다. 이후 left와 right의 반복자를 이동시켜서 마저 코드를 진행한다.
현재 current를 기준으로 모든 절차가 끝났다면 반복자를 증가시켜 기준이되는 값을 바꿔준다.