99클럽 코테 스터디 7일차 TIL + Brute Force 브루트포스, 완전 탐색

✨ 문제 

Count Pairs Whose Sum is Less than Target

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.

 

Example

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target 
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

 

 

https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/description/

 

 

 

✨ 개념

완전 탐색 알고리즘

- 문제의 모든 가능한 수를 시도하여 최적의 방법을 찾는 방법.

- 장점 : 가능한 모든 경우를 고려하기 때문에 정확성 보장

- 단점 : 시간복잡도가 높음.

 

Brute Force 브루트포스 알고리즘

- 완전 탐색의 종류 중 하나로, 가능한 모든 경우의 수를 탐색하여 결과를 도출하는 알고리즘.

- 완전 탐색이 탐색하는 과정에 중점을 둔다면, 브루트포스는 결과를 찾는 것에 중점을 둠.

- 경우의 수가 작을 때 사용할 수 있음.

- 대부분 반복문과 조건문을 통하여 답 도출.

 

 

 

✨ 최종코드

public static int countPairs(List<Integer> nums, int target) {
    int answer = 0;
    Collections.sort(nums);

    for (int i = 0; i < nums.size() - 1; i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if ((nums.get(i) + nums.get(j)) < target)
                answer++;
            else break;
        }
    }

    return answer;
}

 

이중 for문을 사용하여 가능한 모든 조합을 시도하도록 하였다.

 

일단 nums 리스트를 정렬하였는데 이는 정렬을 한 뒤 nums의 i번째 값과 j번째 값을 합하면 어느 순간 target보다 커지는 순간이 오게되는데 그때 그 뒤의 인덱스들을 실행할 필요 없이 break로 종료시키기 위함이다.

nums를 정렬한 뒤 이중 for문을 작성했다. i의 초기값은 0으로 주고 최종값을 nums.size() - 1까지 주었고, j의 초기값은 i + 1, 최종값은 nums.size()으로 주었다.