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


한동안 이걸 도대체 어떻게 풀어야하나 고민을 많이 하다가 결국 다른 사람들은 어떻게 풀었는지 찾아보고 해결한 문제다.

어떻게 하더라도 이중 루프를 피하기는 어려울 것 같아서 그런 것이었는데, 그냥 쓰면 되는거였다.


vector<vector<int>> threeSum(vector<int>& nums)
{
	vector<vector<int>> tRet;

	if (nums.size() > 2)
	{
		//! sort first
		sort(nums.begin(), nums.end());

		//! find from first one
		int nVal = 0;
		int nLow = 0;
		int nHigh = 0;

		for (int i = 0; i < nums.size() - 2; ++i)
		{
			nVal = -nums[i];
			nLow = i + 1;
			nHigh = nums.size() - 1;

			while (nLow < nHigh)
			{
				if (nums[nLow] + nums[nHigh] == nVal)
				{
					tRet.push_back({ nums[i], nums[nLow], nums[nHigh] });
					while (nLow < nHigh && nums[nLow] == nums[nLow + 1]) ++nLow;
					while (nLow < nHigh && nums[nHigh] == nums[nHigh - 1]) --nHigh;
					++nLow;
					--nHigh;
				}
				else if (nums[nLow] + nums[nHigh] < nVal)
				{
					while (nLow < nHigh && nums[nLow] == nums[nLow + 1]) ++nLow;
					++nLow;
				}
				else
				{
					while (nLow < nHigh && nums[nHigh] == nums[nHigh - 1]) --nHigh;
					--nHigh;
				}
			}
		}	//! end of for loop
	}

	sort(tRet.begin(), tRet.end());
	tRet.erase(unique(tRet.begin(), tRet.end()), tRet.end());

	return tRet;
}



다른 사람들의 내용을 보면, 중복이 들어갈 요소가 있어서 해당 부분은 마지막에 정렬을 하고, 다시 중복을 제거하는 코드를 삽입하여 해결했다.

애초에 중복을 넣지 않는 방식으로 해결을 해볼까도 생각했지만, 마땅히 생각나는 것도 없어서 그냥 이정도로 마무리를 했다.

쉬운듯 쉽지않은 문제이다.

'Programming > C,C++' 카테고리의 다른 글

[LeetCode] 78. Subsets  (0) 2018.04.09
[LeetCode] 46. Permutations  (0) 2018.03.26
[LeetCode] 15. 3Sum  (0) 2018.03.26
[LeetCode] 8. String to Integer (atoi)  (0) 2018.03.20
[BOJ] 1003. 피보나치 함수  (0) 2018.03.20
[BOJ] 2293. 동전 1  (0) 2018.02.22

+ Recent posts