[LeetCode] 2300. Successful Pairs of Spells and Potions, Medium

1. 문제

• 정수 배열 spells와 potions가 주어질 때, 아래 조건을 만족하는 배열을 반환하라.
  • 각 spell * 각 potion이 success를 초과하는 개수를 담는다.
  • spell 별로 시행해서 배열에 담는다.

2. 해결

function successfulPairs(spells: number[], potions: number[], success: number): number[] {
    
    const ans = [];

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

    for(let spell of spells) {
        let left = 0, right = potions.length - 1;
        let validIndex = potions.length;

        while(left <= right) {
            const mid = Math.floor((left + right) / 2);
            const res = potions[mid] * spell;

            if(res >= success) {
                validIndex = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        ans.push(potions.length - validIndex)
    }

    return ans;
};

• 문제 접근은 잘 했는데 아래 부분을 놓쳤다.
  • 이진 탐색을 위한 정렬을 단순히 sort()만 사용 -> 문자열 유니코드 정렬이 이루어지므로 숫자 정렬은 정확하지 않다.
  • 중간값을 찾아 조건을 만족하고 끝이 아니라, 조건을 만족하는 가장 왼쪽 인덱스를 찾아야 하므로 왼쪽도 탐색해주어야 한다. (validIndex 찾는 과정)