Number of Subsequences That Satisfy the Given Sum Condition

문제설명

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 10^9 + 7.

제한사항

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= target <= 106

입출력 예

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

행동영역(알고리즘을 설계하는 사고과정)

1. 요소탐색
   어떤 배열내의 최소값과 최소값의 합이 target보다 커지면 안되기 때문에 범위의 문제라고 이해하여, while문으로 두 요소의 합이 target보다 커질때 최초의 순간을 찾는다.

• 막상 코드를 짜다보니 while문으로도 안되어서 이중 for문으로 풀고 있었다.

2. 배열 정리하기
   target보다 커지는 최초의 순간을 기점으로 target보다 확실히 커질 수 있는 요소들을 모두 제거한 나머지 요소들을 가지고 있는 배열을 반환한다.

3. 규칙을 만족하는 배열의 경우를 구하기

• 맨 처음에는 조합으로 배열의 경우를 구하면 될거라고 생각했지만
  1번 케이스를 잘 살펴보니 조합으로 문제를 풀 수 없는 이유가 [5,6]처럼 2번 과정을 통과한 요소라도 조합에 따라 규칙을 통과하지 못하는 경우가 발생하기 때문에 for문과 if문으로 일일히 확인해야할 것 같다.

• 20분만에 드디어 규칙을 파악했다. 확실하게 될 수 없는 요소를 제외시키고 나면, 모든 요소들을 길이가 1인 배열부터 모든 요소들을 포함하고 있는 배열의 길이까지 모든 배열들을 만들어서 나열 후, 그 배열들을 각각 최소값과 최대값의 합연산을 통해 target보다 작은지 비교해야한다.

평가 : 이 문제의 넌센스는 길이가 1인 배열에서 최소값과 최대값을 적용시킬 수 있다는 발상이었다.

답

내가 쓴 답

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function (nums, target) {
  let arr = []
  for(i=0; i<nums.length; i++) {
    for(j=0; j<nums.length; j++) {
      if(nums[i] + nums[j]<= target) {
        arr.push(nums[i], nums[j])
      }
    }
  }
const uniqueSet = new Set(arr);
const processed = Array.from(uniqueSet);

  let final = []
  for (let i = 0; i < processed.length; i++) {
    final.push([processed[i]])
    for (let j = i+1; j < processed.length; j++) {
      final.push(processed.slice(i, j + 1));
    }
  }

  let result = []
  for(let i=0; i<final.length; i++) {
    if(Math.min(...final[i])+Math.max(...final[i])<=target) {
      result.push(final[i])
    }
  }
  return result.length 
};
//[ [ 3 ], [ 3, 5 ], [ 3, 5, 6 ] ] 

[ [ 3 ], [ 3, 5 ], [ 3, 5, 6 ] ] 이렇게 나왔는데, 이 코드의 문제점 하나는 [3,6]을 고려하지 않았다는 것이다. 그래서 이 부분을 보완해서 다시 코드를 짰다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function (nums, target) {
  function getAllSubsets(array) {
    let result = [[]];

    for (let i = 0; i < array.length; i++) {
      const len = result.length;
      for (let j = 0; j < len; j++) {
        const subset = result[j].concat(array[i]);
        result.push(subset);
      }
    }

    // 공집합 제거
    result.shift();

    return result;
  }

  let subsets = getAllSubsets(nums);

  let result = [];
  for (let i = 0; i < subsets.length; i++) {
    let minMaxSum = Math.min(...subsets[i]) + Math.max(...subsets[i]);
    if (minMaxSum <= target) {
      result.push(subsets[i]);
    }
  }

  return result.length;
};

Input: nums = [3,5,6,7], target = 9
Output: 4

Input: nums = [3,3,6,8], target = 10
Output: 6

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61

이 세가지의 경우에 대해서는 코드가 잘 작동되었지만,

Input: nums = [14,4,6,6,20,8,5,6,8,12,6,10,14,9,17,16,9,7,14,11,14,15,13,11,10,18,13,17,17,14,17,7,9,5,10,13,8,5,18,20,7,5,5,15,19,14]

Output : 22

의 경우는 자바스크립트 힙 메모리 부족 때문에 통과하지 못했다. 그래서 이 부분을 고려하여 어떻게 코드를 짤지 고민하던 중에 투 포인터 알고리즘을 찾아서 다시 수정을 했다.

수정한 답

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function (nums, target) {
  const MOD = 1000000007;
  let n = nums.length;
  let res = 0;
  let left = 0;
  let right = n - 1;
  let power = new Array(n).fill(0);
  power[0] = 1;

  // 미리 2의 거듭제곱을 계산하여 저장
  for (let i = 1; i < n; i++) {
    power[i] = (power[i - 1] * 2) % MOD;
  }

  // 입력 배열을 오름차순으로 정렬
  nums.sort((a, b) => a - b);

  // 투 포인터 알고리즘을 사용하여 조건에 맞는 부분집합 개수 계산
  while (left <= right) {
    if (nums[left] + nums[right] <= target) {
      res = (res + power[right - left]) % MOD;
      left++;
    } else {
      right--;
    }
  }

  return res;
};

다른풀이

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function(nums, target) {
    const MOD = 1000000007;

    nums = nums.sort((a, b) => a - b);

    const pows = [1];
    
    for (let i = 1; i < nums.length; i++) {
        pows.push(pows[i - 1] * 2 % MOD);
    }
    
    let left = 0;
    let right = nums.length - 1;
    let ans = 0;

    while (left <= right) {
        if (nums[left] + nums[right] > target) {
            right--;
        } else {
            ans = (ans + pows[right - left]);
            left++;
        }
    }

    return ans % MOD;
};

속도 백분위

피드백

처음짰던 코드와 수정한 코드와의 비교

(처음짰던 코드)

모든 부분집합을 생성하기 위해 백트래킹을 사용한다.
각 부분집합의 최소값과 최대값의 합을 계산하고, 그 합이 target보다 작거나 같으면 결과 배열에 추가한다. 결과 배열의 길이를 반환한다.

(수정한 코드 코드)

nums 배열을 오름차순으로 정렬한다.
2의 거듭제곱을 미리 계산하여 power 배열에 저장한다. 이 값들은 후에 조건에 맞는 부분집합 개수를 계산하는 데 사용된다.
투 포인터 알고리즘을 사용하여 조건에 맞는 부분집합 개수를 계산합니다.
계산된 결과를 반환합니다.

첫 번째 코드는 백트래킹을 사용하여 모든 부분집합을 생성한 다음 조건에 맞는 부분집합을 찾는다. 이 방법은 비효율적이며 시간 복잡도가 높다.

두 번째 코드는 정렬과 투 포인터 알고리즘을 사용하여 조건에 맞는 부분집합을 효율적으로 찾는다. 이 방법은 시간 복잡도가 낮아 더 빠르게 동작합니다.
첫 번째 코드는 결과 배열의 길이를 반환하는 반면, 두 번째 코드는 결과를 바로 계산하여 반환한다.

※ 이런식으로 알고리즘의 차이를 비교하여 알고리즘의 방법을 익히고 복습해야겠다.

https://www.notion.so/5-13-7feee567c42b4dc8bc302885e3bce66a

투 포인터 알고리즘에 대한 자세한 내용은 노션을 참고하자.

---

지금 시점에서 내가 원하는 알고리즘을 매서드로 얼마나 잘 구현하느냐가 중요하기보다(이미 익숙해질 부분들은 익숙해졌기에) 문제를 풀기위해 어떻게 알고리즘을 설계할건지 사고하는 과정을 연습하는게 훨씬 더 중요하다.
만약에 매서드에 익숙하지 않아 원하는 알고리즘을 구현해내는 실력이 부족하더라도 문제는 앞으로도 꾸준히 매일 풀 것이기 때문에 문제를 정상적으로 제대로 푼다면, 익숙해질 부분이다.

뿐만 아니라, 알고리즘을 확실하게 설계하면 어떻게 매서드를 작성할건지 머리속에서도 정리가 되기 때문에 부담도 줄어든다.

알고리즘을 문제를 풀다보면 문제해결을 해나가는 과정의 스타일을 볼 수 있었다.
나는 주로 백트래킹(가지치기)를 사용한다. 그러다보니 테스트코드는 다 통과하더라도 최종 테스트에서 메모리 문제가 종종 걸리는데, 나의 생각의 수준을 뛰어넘기 위해 어떻게 해야할지 곰곰히 생각해봐야겠다. 알고리즘 지식이 필요할까? 아니면 센스가 필요할까?

[느낀점]

① 규칙을 찾는건 쉬운데, 그 규칙을 알고리즘으로 바꿀때 테스트코드로 나온 케이스들의 결과가 어떻게 도출되었는지 미묘한 차이를 정형화 시키는게 쉽지않다.

② 내가 세운 아이디어를 테스트코드로 검증할때 정말 꼼꼼하게 확인해야하는 것 같다.

③ 문제랑 테스트코드 대충읽고 규칙에 대해 제대로 이해도 안하고 문제를 풀려고 하다보니 자꾸 말리게 되는 것 같다.

④ 테스트코드는 규칙 확정시키기 위해 필요한 힌트를 제공해주기 때문에 매우 중요하다.

복습

1. push() 함수에 두가지 이상요소 넣기

arr.push(arr[i], arr[j]);

2. set()

// 배열의 중복을 제거하기 위해 Set 객체 생성
const uniqueSet = new Set(arrayWithDuplicates);

// Set 객체를 다시 배열로 변환
const uniqueArray = Array.from(uniqueSet);

3. Max함수와 Min함수
Math.min()과 Math.max() 함수는 인자로 숫자를 받는다. 따라서 배열을 전달하려고 한다면, 배열의 요소를 먼저 전달하고 그 값을 배열로 다시 만들어줘야한다.