Skip to main content

[투 포인터] 연습

3개의 숫자 중에서 먼저 가장 작은 수를 하나 뽑고, 나머지 숫자 조합을 찾는 방법이다.

1. num 배열을 정렬한 후 제일 앞 원소를 조합의 첫 번째 숫자로 지정한다.

  • i를 기준으로 nums[i] 먼저 선택하고, 나머지 두 수를 양쪽 끝에서 투 포인터로 탐색하는 방법이다.

2. 그 뒤에 있는 숫자들 중 조건을 만족하는 나머지 2개의 숫자를 찾는다.

  • 첫번째 숫자의 바로 다음 숫자의 index를 left로 지정하고 가장 마지막 index를 right로 지정하기
  • left = i + 1 → 첫 번째 숫자 바로 다음
  • right = nums.length - 1 → 배열 마지막 숫자

3. 합 계산후 포인터 이동하기

첫 번째 숫자 + nums[left] + nums[right] 합에 따라 left와 right 값을 적절하게 변경하는 과정이다.

숫자의 합은 이렇게 표현할수 있다. 

sum = nums[i] + nums[left] + nums[right]

세 숫자의 합은 아래 세 가지 경우로 나뉜다.

  • sum > 0 : sum을 줄여야 하기 때문에 right--
  • sum < 0 : sum을 늘려야 하기 때문에 left++
  • sum == 0 : 조합을 찾았기 때문에 left++, right--

nums 배열을 순회하면서 이 과정을 반복한다.

sum의 값에 따라 left와 right의 값을 변경할 수 있는 이유는 nums 배열이 정렬되어 있기 때문이다.
nums[left] <= nums[left + 1] 과 nums[right] >= nums[right - 1]은 항상 참이기 때문이다.
import java.util.Arrays;

class Solution {
    public int threeSumCount(int[] nums) {
        Arrays.sort(nums); // 정렬 필수
        int n = nums.length;
        int count = 0; // 합이 0인 조합 개수

        for (int i = 0; i < n - 2; i++) {
            // 첫 번째 숫자가 배열 첫 원소가 아닌 경우 
            // AND nums[i] == nums[i - 1] 앞에서 이미 같은 값으로 탐색 했음
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 중복 방지

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    count++; // 조합 추가 대신 카운트 증가
                    left++;
                    right--;
                    // 중복 원소 스킵
                    // 이전 left 값과 같으면, 이미 같은 조합을 센 것이므로 건너 뛰고 다음 숫자(left++)로 이동
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    // 이전 right 값과 같으면, 마찬가지로 건너 뛰고 다음 숫자(right--) 로 이동
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < 0) {
                    left++;  // 합을 키워야 함
                } else {
                    right--; // 합을 줄여야 함
                }
            }
        }

        return count; // 최종 개수 리턴
    }
}

중복제거 

while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
  • nums[left] == nums[left - 1]
    → 이전 left 값과 같으면, 이미 같은 조합을 센 것이므로 건너뛰고 다음 숫자(left++)로 이동
  • nums[right] == nums[right + 1]
    → 이전 right 값과 같으면, 이미 같은 조합을 센 것이므로 건너뛰고 다음 숫자(right--)로 이동

정렬 덕분에 중복 제거가 가능하다. 같은 숫자는 연속으로 모여 있기 때문이다.

따라서 while문으로 연속된 중복 원소를 건너 뛰면 중복 조합 없이 탐색이 가능하다.

nums = [-1, -1, -1, 2, 2]
i=0, left=1, right=4

1. sum = 0 → count++
2. left++ → left=2, nums[2]==nums[1] → 건너뜀 → left=3
3. right-- → right=3, nums[3]==nums[4] → 건너뜀 → right=2
4. left >= right → 탐색 종료

뭐가 안되면 제일 먼저 할 일

  • ​코드를 한글로 써보기
  • 손으로 직접 반복문 써보기
  • 어렵지만 노력과 시간으로 커버해야 함


Back to top