[Leetcode] 2824. 합이 목표보다 작은 쌍의 개수 계산

1. 문제

문제 설명

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

배열 nums와 정수 target이 주어졌을 때, 배열 내에서 두 요소의 합이 target보다 작은 쌍 (i, j)의 개수를 찾는 문제

• 0 <= i < j < n
• nums[i] + nums[j] < target

제한사항

• 1 <= nums.length == n <= 50
• -50 <= nums[i], target <= 50

입출력의 예

예시 1:

입력: nums = [-1,1,2,3,1], target = 2
출력: 3
설명: 명령문의 조건을 충족하는 인덱스 쌍이 3개 있습니다.

• 0 < 1이고 nums[0] + nums[1] = 0 < target이므로 (0, 1)
• 0 < 2이고 nums[0] + nums[2] = 1 < target이므로 (0, 2)
• 0 < 4이고 nums[0] + nums[4] = 0 < target이므로 (0, 4)
  nums[0] + nums[3]이 목표보다 엄격하게 작지 않기 때문에 (0, 3)은 계산되지 않습니다.

2. 풀이 과정

배열의 모든 가능한 쌍을 확인해서 주어진 조건을 만족하는지 검사하는 문제이다.
1. 배열 nums의 모든 가능한 쌍 (i, j)를 탐색하면서 nums[i] + nums[j] < target 조건을 만족하는지 확인한다.
2. 이중 루프를 사용하여 i와 j의 모든 가능한 조합을 검사한다.
3. i는 0부터 n-2까지, j는 i+1부터 n-1까지 순회한다.

3. 최종 코드

import java.util.List;

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        int count = 0;
        int n = nums.size();

        for(int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if(nums.get(i) + nums.get(j) < target) {
                    count++;
                }
            }
        }

        return count;
    }
}

마무리

다른 풀이가 있을까 딱히 떠오르는 풀이가 없다. 좀 더 배우고 다시 풀어봐야겠다.