https://leetcode.com/problems/3sum/
📕 문제 설명
정수 배열 nums가 주어질 때 i, j, k에 대해 다음을 만족하는 정수 배열 triplet들 찾기
- i, j, k는 모두 달라야 한다.
- nums[i] + nums[j] + nums[k] = 0
triplet은 중복 없이 반환한다.
- Input
정수 배열 num - Output
조건 만족하는 triplet 반환
예제
풀이
시도 1.
전체 케이스 보면서 만약 이미 존재하는 것이 없는 경우만 추가하는 방법
실패 (시간초과)
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
List<IList<int>> threeSumList = new List<IList<int>>();
for (int i = 0; i < nums.Length; i++)
{
for (int j = i+1; j < nums.Length; j++)
{
for (int k = j+1; k < nums.Length; k++)
{
if (nums[i] + nums[j] + nums[k] == 0)
{
List<int> numList = new List<int>() {nums[i], nums[j], nums[k]};
numList.Sort();
var numQuery = from num in threeSumList
where (num[0] == numList[0] && num[1] == numList[1] && num[2] == numList[2])
select num;
if (numQuery.Count() == 0) threeSumList.Add(numList);
}
}
}
}
return threeSumList;
}
}
시도 2.
실패 (시간초과)
가능한 케이스들을 생각해서 나눠서 풀었는데도 시간 초과가 났다. c#에서 리스트끼리 값에 대한 비교를 하는 연산이 비싸다 생각되어 이 부분을 바꿔야겠다고 생각했다.
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
List<IList<int>> threeSumList = new List<IList<int>>();
List<int> posNums = new List<int>();
List<int> negNums = new List<int>();
HashSet<int> posSet = new HashSet<int>();
HashSet<int> negSet = new HashSet<int>();
int zero = 0;
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] > 0)
{
posNums.Add(nums[i]);
posSet.Add(nums[i]);
}
else if (nums[i] < 0)
{
negNums.Add(nums[i]);
negSet.Add(nums[i]);
}
else zero++;
}
if (zero > 0)
{
var numQuery = from num in posNums where negNums.Contains(-num) select num;
foreach(int num in numQuery.ToHashSet())
{
threeSumList.Add(new List<int>() {-num, 0, num});
}
if (zero > 2) threeSumList.Add(new List<int>() {0, 0, 0});
}
bool isRepeated = false;
for (int i = 0; i < posNums.Count; i++)
{
for (int j = i+1; j < posNums.Count; j++)
{
int value = -(posNums[i] + posNums[j]);
if (negSet.Contains(value))
{
List<int> temp = new List<int>() {posNums[i], posNums[j], value};
temp.Sort();
foreach(List<int> threeSum in threeSumList)
{
if (threeSum.SequenceEqual(temp))
{
isRepeated = true;
break;
}
}
if(!isRepeated) threeSumList.Add(temp);
else isRepeated = false;
}
}
}
for (int i = 0; i < negNums.Count; i++)
{
for (int j = i+1; j < negNums.Count; j++)
{
int value = -(negNums[i] + negNums[j]);
if (posSet.Contains(value))
{
List<int> temp = new List<int>() {negNums[i], negNums[j], value};
temp.Sort();
foreach(List<int> threeSum in threeSumList)
{
if (threeSum.SequenceEqual(temp))
{
isRepeated = true;
break;
}
}
if(!isRepeated) threeSumList.Add(temp);
else isRepeated = false;
}
}
}
return threeSumList;
}
}
풀이 1.
위랑 접근 방식은 동일하다. hashSet에서는 동일한 값들을 가진 리스트가 같은 것으로 처리되지 않기 때문에 (새로운 인스턴스 생성하듯이 리스트를 만들기에 주소가 다르게 저장되기 때문일것으로 보임..!) string으로 처리하도록 변경했다. 3가지 값을 찾으면 이를 정렬한 다음 string에 각 숫자 별로 구분을 위해 ","를 붙여 저장한 다음 hashSet에 넣어 동일한 값들을 처리했다. 모든 가능한 숫자 조합 찾은 후 마지막에 "," 기준 split해서 정답에 추가해줬다.
가능한 케이스들은 다음과 같이 정의할 수 있다.
1. 0이 3번 나오는 경우
2. 0이 1개에 양수 음수 조합
3. 양수 2개 음수 1개
4. 양수 1개 음수 2개
따라서 다음의 케이스로 나눠 각각 합쳐준 방식!
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
List<IList<int>> threeSumList = new List<IList<int>>();
HashSet<string> temp = new HashSet<string>();
List<int> posNums = new List<int>();
List<int> negNums = new List<int>();
HashSet<int> posSet = new HashSet<int>();
HashSet<int> negSet = new HashSet<int>();
int zero = 0;
// 먼저 양수, 음수, 0으로 나눈다
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] > 0)
{
posNums.Add(nums[i]);
posSet.Add(nums[i]);
}
else if (nums[i] < 0)
{
negNums.Add(nums[i]);
negSet.Add(nums[i]);
}
else zero++;
}
// 0이 1개 이상인 경우 (1,2 케이스 확인)
if (zero > 0)
{
// 2번 케이스 가능한 값 뽑기
var numQuery = from num in posSet where negSet.Contains(-num) select num;
foreach(int num in numQuery)
{
threeSumList.Add(new List<int>() {-num, 0, num});
}
// 1번 케이스
if (zero > 2) threeSumList.Add(new List<int>() {0, 0, 0});
}
// 양수 2개 음수 1개 조합
for (int i = 0; i < posNums.Count; i++)
{
for (int j = i+1; j < posNums.Count; j++)
{
int value = -(posNums[i] + posNums[j]);
if (negSet.Contains(value))
{
List<int> t = new List<int>() {posNums[i], posNums[j], value};
t.Sort();
string tempS = t[0].ToString() + "," +t[1].ToString() + "," + t[2].ToString();
temp.Add(tempS);
}
}
}
// 음수 2개 양수 1개 조합
for (int i = 0; i < negNums.Count; i++) // -1 -1 -4
{
for (int j = i+1; j < negNums.Count; j++)
{
int value = -(negNums[i] + negNums[j]);
if (posSet.Contains(value))
{
List<int> t = new List<int>() {negNums[i], negNums[j], value};
t.Sort();
string tempS = t[0].ToString() + "," +t[1].ToString() + "," + t[2].ToString();
temp.Add(tempS);
}
}
}
foreach(string tempS in temp)
{
string[] t = tempS.Split(",");
threeSumList.Add(new List<int>() {int.Parse(t[0]), int.Parse(t[1]), int.Parse(t[2])});
}
return threeSumList;
}
}결과 1.
풀이 2.
한 값을 target으로 잡고 나머지를 두 포인터를 두고 보면서 가능한 경우 추가하는 케이스
- 배열 정렬
- 제일 처음 값부터 차례로 보면서 left pointer, right pointer 정의 (left는 현재 보는 index 바로 다음 값, right는 맨끝 인덱스로 매번 설정)
3-1) 만약 i와 lp, rp가 가리키는 값들의 합이 0이면 결과에 추가 후 left pointer를 동일한 값 아닌 것 만날 때 까지 이동
3-2) 만약 합이 0보다 크면 양수 값의 절대 값을 낮추기 위해 right pointer 낮추기
3-3) 만약 합이 0보다 작으면 음수 값의 절대 값을 낮추기 위해 left pointer 올리기
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
List<IList<int>> threeSumList = new List<IList<int>>();
Array.Sort(nums);
int lp = 0;
int rp = nums.Length;
int sum = 0;
for (int i = 0; i < nums.Length; i++)
{
if (i > 0 && nums[i] == nums[i-1]) continue; // 이전에 본 값이랑 같은 케이스
lp = i + 1;
rp = nums.Length - 1;
while (lp < rp)
{
sum = nums[i] + nums[lp] + nums[rp];
if (sum == 0)
{
threeSumList.Add(new List<int>() {nums[i], nums[lp], nums[rp]});
lp++;
while (lp < rp && nums[lp] == nums[lp-1])
{
lp++;
}
}
else if (sum > 0) rp--; // 현재 합이 양수면 양수 값의 절대 값을 낮춰야함
else lp++; // 현재 합이 음수면 음수 값의 절대 값을 낮춰야함
}
}
return threeSumList;
}
}결과 2.
하나씩 심어 나가는 개발 농장🥕 (블로그 이전중)