Daily LeetCode Challenge - 2300. Successful Pairs of Spells and Potions

Problem From.
https://leetcode.com/problems/successful-pairs-of-spells-and-potions/

오늘 문제는 주문 배열 spells 와 포션 배열 potions 가 주어졌을때, 각각의 원소의 곱이 success 보다 크면 그 갯수를 세어서 배열에 넣어 리턴하는 문제였다.

하나씩 곱해보고 비교해보는 O(N^2) 의 실행시간을 가지면 시간 초과로 통과하지 못하므로, 비교하는 곳의 로직을 이진탐색으로 풀었다.

potions 를 오름차순으로 정렬한 뒤, 시작 인덱스 start 와 끝 인덱스 end 를 두고, 가운데 인덱스를 가져온다. spell 의 원소와 potions 의 가운데 인덱스 원소를 곱한 수가 success 보다 크면 끝 인덱스를 가운데 인덱스의 -1 로 하고 더 작으면 시작 인덱스를 가운데 인덱스의 +1 로 한다. 위 과정을 거치다가 이진탐색이 끝나면 potions 의 총 길이에서 가운데 인덱스를 빼면, 나머지 success 보다 큰 값들의 개수가 나오게 된다.

class Solution {
    fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        var answer = IntArray(spells.size) { 0 }
        potions.sort()
        spells.forEachIndexed { index, spell ->
            answer[index] = binarySearch(spell, potions, success)
        }
        return answer
    }
    
    private fun binarySearch(spell: Int, potions: IntArray, success: Long) : Int {
        var start = 0
        var end = potions.size - 1
        while(end >= start) {
            var mid = (end + start) / 2
            val power = spell.toLong() * potions[mid].toLong()
            if(power >= success) end = mid - 1
            else start = mid + 1
        }
        return potions.size - start
    }
}