230731 알고리즘 4-합계 자바스크립트 문제풀이

230731 알고리즘 4-합계 자바스크립트 문제풀이

 

문제

정수 배열 nums와 정수 값 target이 주어질 때,

배열 nums에서 4개의 원소를 선택하여 합 했을 때, target과 같은 값이 되는 모든 부분 배열을 출력하라

4Sum - LeetCode

 

문제 접근

원소의 합계를 합하기 위해서 nums 배열에서 4개의 원소를 선택해야 한다.

• for문을 통해 1,2번째 원소 선택한다
• left,right 포인터를 통해 3,4번째 원소를 선택하고 합계를 구하고 target 값을 비교해 포인터 위치를 조절한다

 

문제 풀이

1. 먼저 배열을 정렬하여 순서를 오름차 순으로 만든다.
2. for문을 2번 이용하여 각각 첫 번째 원소, 두 번째 원소를 선택한다
3. 이때 if문과 continue를 사용하여 값이 같은 원소는 건너 뛴다.
4. 세 번째, 네 번째 원소를 선택하기 위해 각각 포인터를 left, right로 만든다
5. left는 두 번째 원소의 다음 인덱스, right는 마지막 원소 인덱스에서 시작한다
6. left와 right가 만날 때까지 while을 통해 반복하여 4개의 원소 합을 구한다
   1. 이때 4개의 원소는 nums[i], nums[j], nums[left], nums[right]이다
   2. 4개 원소의 총합인 sum 값이 target보다 작으면 left 인덱스를 증가시켜 더 큰 합계를 찾을 수 있다
   3. 반대로 sum 값이 target보다 크면 right 인덱스를 감소시켜 더 작은 합계를 찾을 수 있다.
   4. sum 값과 target 값이 일치하면 다시 while문을 사용하여 중복 원소를 건너 뛰고,
      left값을 증가, right 값을 감소시켜 범위를 축소시킨다

function fourSum(nums, target) {
  // 배열 정렬
  nums.sort((a, b) => a - b);
  // 결과 배열 초기화
  const results = [];

  //첫 번째 원소 탐색
  for (let i = 0; i < nums.length - 3; i++) {
    //중복된 첫 번째 원소 건너뛰기
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    // 두 번째 원소 탐색
    for (let j = i + 1; j < nums.length - 2; j++) {
      //중복된 두 번째 원소 건너뛰기
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;

      //두 개의 포인터 초기화
      let left = j + 1; // 두 번째 원소 다음 인덱스
      let right = nums.length - 1; // 마지막 원소 인덱스

      while (left < right) {
        //left와 right로 세 번째, 네 번째 원소를 선택하여 합계 계산
        const sum = nums[i] + nums[j] + nums[left] + nums[right];

        if (sum === target) {
          // 합계가 타겟과 일치하는 경우
          results.push([nums[i], nums[j], nums[left], nums[right]]);

          // 중복 원소 건너 뛰기
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;

          //left를 증가, right를 감소시켜 범위 축소
          left++;
          right--;
        } else if (sum < target) {
          // 합계가 타겟보다 작은 경우 -> left를 오른쪽으로 이동
          left++;
        } else {
          // 합계가 타겟보다 큰 경우 -> right를 왼쪽으로 이동
          right--;
        }
      }
    }
  }

  return results;
}

코드 출처: https://leetcode.com/problems/4sum/solutions/581600/javascript-using-4-pointers-beats-96/

JavaScript using 4 pointers beats 96% - 4Sum - LeetCode