2300. Successful Pairs of Spells and Potions

 

📌 Problem Link :

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

 

❌ Wrong Answer :

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] result = new int[n];

        Arrays.sort(potions);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                long spell = spells[i];
                long potion = potions[j];
                if (spell * potion >= success) {
                    result[i] = m - j;
                    break;
                }
            }
        }
        return result;
    }
}

 

✅ Accepted :

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] result = new int[n];

        Arrays.sort(potions);
        for (int i = 0; i < n; i++) {
            long spell = spells[i];
            int idx = lowerBound(potions, spell, success);
            result[i] = m - idx;
        }
        return result;
    }

    private int lowerBound(int[] potions, long spell, long success) {
        int left = 0, right = potions.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            long product = spell * potions[mid];

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

 

🧐 Review :

 입력으로 주어지는 배열의 길이가 10^5 정도라면, 시간 복잡도가 O(N^2)인 알고리즘으로 접근할 경우 사실상 시간 초과가 발생할 가능성이 매우 높다. 그래서 처음부터 이분 탐색을 떠올리긴 했지만, 구체적인 접근 방법이 쉽게 정리되지 않았다.

우선은 모든 테스트 케이스를 통과하지 못하더라도 하나라도 정답이 나오는 코드를 먼저 작성하고, 이후에 연산 횟수를 줄이면서 점진적으로 리팩토링하는 방향을 잡았다.

 

초기에는 이중 for문을 사용해 spell과 potion의 곱이 success보다 큰 경우를 직접 세는 방식으로 구현했다. 하지만 모든 연산을 전부 수행할 필요는 없다고 판단했다. potion 배열을 오름차순으로 정렬하면, spell * potion 값이 success 이상이 되는 첫 번째 인덱스를 찾은 이후에는 그 뒤의 값들이 모두 조건을 만족한다는 사실을 이용할 수 있기 때문이다. 따라서 이 인덱스를 찾아 남은 원소의 개수를 계산하면 효율적으로 답을 구할 수 있다고 생각했고, 이를 코드로 구현했다.

 

코드를 제출한 결과 일부 테스트 케이스는 통과했지만, 특정 케이스에서는 결과값이 0이 나오는 문제가 발생했다. 원인을 살펴보니 spell과 potion의 곱이 int형의 범위를 초과하면서 오버플로우가 발생하고 있었다. 두 변수를 모두 long으로 형변환하여 계산하니 해당 문제는 해결되었고, 모든 테스트 케이스에서 정상적인 결과가 출력되었다.

 

하지만 여전히 일부 케이스에서는 시간 초과가 발생했다. 이 시점부터는 단순한 반복문 최적화로는 한계가 있다고 판단했고, GPT의 도움을 받아 코드를 개선했다.

 

 이번 문제를 통해 단순히 “빠른 알고리즘을 써야 한다”는 인식에서 한 단계 더 나아가, 정렬과 이분 탐색을 결합한 효율적인 사고 과정의 중요성을 다시 느꼈다. 또한, 자료형에 따라 연산 결과가 달라질 수 있다는 점 역시 다시 한 번 실감했다. 앞으로는 문제를 처음 접근할 때부터 시간 복잡도와 자료형의 범위를 함께 고려하며, 불필요한 연산을 줄이는 방향으로 사고하는 습관을 꾸준히 다듬어야겠다.