JAVA 자료구조 (배열) - 세수의 합(💡투 포인터)

세수의 합

 

풀이1 - 투 포인터로 합 계산

정렬한 다음에 i를 축으로 하고, 중복된 값을 건너뛰게 한 부분은 다음과 같이 풀이 #1과 동일하다.

if(i > 0 && nums[i] == nums[i -1])
	countinue;

중복된 값이 있을 경우 continue로 건너뛴다. 

 

그림 7-8 투 포인터 풀이

 

left = i + 1;
right = nums.length -1;
while (left < right)
	sum = nums[i] + nums[left] + nums[right];
    ...

 

i 의  다음 지점과 마지막 지점을 위 그림과 같이 left, right로 설정하고 간격을 좁혀가며 sum을 계산한다. 

if(sum < 0)
  left +=1
else if(sum > 0)
  right -=1
else{
  results.add(Array.asList(nums[i], nums[left], nums[right]));
  
  while(left < right && nums[left] == nums[left + 1])
  left+=1;
  while(left < right && nums[right] == nums[right -1])
  right-=1
  
}

 

합 sum이 0 보다 작다면 값을 더 키워야 하므로 left를 우측으로 이동하고, 0보다 크다면 값을 더 작게하기 위해 right를  좌측으로 이동한다. sum이 0이면 정답이므로, 이 경우 결과를 리스트 변수 result에 추가한다. 추가한 다음에는 left, right 야 옆으로 동일한 값이 있을 수 있으므로 같은 정답이 두번 나오지 않도록 left += 1, right -= 1을 반복해서 스킵하도록 처리한다.

 

left += 1;
right -= 1;

 

마지막으로 left를 한 칸 우측으로, right를 한칸 좌측으로 더 이동하고 다음으로 넘긴다. 얼핏 생각해보면 left 또는 right 둥 중 하나만 이동해야 하는 게 아닌가 싶지만, 어차피 sum이 0인 상황이므로 어느 한쪽만 이동해서 정답이 될 수 없다. 나머지 다른 정답을 찾으려면 결국 둘 다 모두 움직여야 한다.

 

정리된 코드

public List<List<Integer>> solution(int [] nums) {
    int sum, left, right;
    List<List<Integer>> results = new ArrayList<>();
    Arrays.sort(nums);

    for(int i = 0; i < nums.length; i++){
        //중복된 값 건너 뛰기
        if (i > 0 && nums[i] == nums[i - 1])
            continue;

    //간격을 좁혀며 합 sum 계산
    left = i + 1;
    right = nums.length -1;
    while(left < right) {
        sum = nums[i] + nums[left] + nums[right];
            //합이 0보다 작다면 왼쪽 포인터 이동
            if (sum < 0)
                left += 1;
            //합이 0보다 크면 오른쪽 포인터 이동
            else if (sum > 0)
                right -= 1;
            else {
                //합인 경우 정답 List에 해당하는 값들을 넣어준다.
                results.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                //left 포인터가 연속으로 같은 수로 되어 있을때는 한칸씩 오른쪽으로 이동
                while (left < right && nums[left] == nums[left + 1])
                    left += 1;
                //right 포인터가 연속으로 같은 수로 되어 있을때는 한칸씩 왼쪽으로 이동
                while (left < right && nums[right] == nums[right - 1])
                    right -= 1;

                //i를 기준으로 정답이 나온 상태에서
                //연속된 숫자가 있을 경우 while문을 사용해 모두 한칸씩 이동한 시켰으므로
                //양쪽 모두 이동해야 새로운 조합의 0을 찾을 수 있다.
                left += 1;
                right -= 1;
            }

        }
    }

    return results;
}

 

시간의 복잡도가 O(n³)에서 O(n²) 줄어들었다.

 

💡 투 포인터

앞서 풀이에서 투 포인터(Two Pointers)라는 기법이 지속적으로 등장했다. 투 포인터란 무엇이며 어떤 기법을 말하늘 걸까?

 

여러 가지 방식이 있지만, 대개는 시작점과 끝점 다른 말로 왼쪽 끝과 오른쪽 끝 포인터 두 지점을 기준으로 하는 문제 풀이 전략을 얘기한다. 범위를 좀혀나가기 위해서는 일반적으로 배열이 정렬되어 있을 때 좀 더 유용하다. 앞서 풀이한 9번  '세 수 의 합' 문제 도한 정렬된 배열을 이용하는 대표적인 투 포인터 풀이를 보여둔다. 해당 문제 풀이에서는 기존 O(n³)풀이를 투 포인터 기법을 적용해 O(n²)으로 풀이하는 획기적인 해법을 제시했다.

 

투 포인터는  주로 정렬된 배열을 상대로 하며, 2개의 포인터가 좌우로 자유롭게 움직이며 문제를 풀이한다. 이 때문에 투 포인터라는 이름이 붙었다. 

 

사실 투포인터에 대해서는 아직까지 명확하게 제대로 정된 것이 없다. 일반적으로 알고리즘 교재에 등자하지 않기도한다. 아울러 설명 주체에 딸라 정의도 조금씩 다르다. 특히 슬라이딩 윈도우와 여러 모로 비슷한 점이 많은데, 이후 슬라이딩 윈도우와 투포 인터의 공통점과 차이점을 자세히 살펴본다.

 

 

[출처 - 자바 알고리즘 인터뷰 with 코틀린 , 저 박상길]

https://www.onlybook.co.kr/entry/java-algorithm-interview