Medium - Find Positive Integer Solution for a Given Equation

https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/submissions/

LeetCode - The World's Leading Online Programming Learning Platform

문제 설명

Given a callable function f(x, y) with a hidden formula and a value z, reverse engineer the formula and return all positive integer pairs x and y where f(x,y) == z. You may return the pairs in any order.

While the exact formula is hidden, the function is monotonically increasing, i.e.:

• f(x, y) < f(x + 1, y)
• f(x, y) < f(x, y + 1)

The function interface is defined like this:

interface CustomFunction {
public:
  // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
  int f(int x, int y);
};

We will judge your solution as follows:

• The judge has a list of 9 hidden implementations of CustomFunction, along with a way to generate an answer key of all valid pairs for a specific z.
• The judge will receive two inputs: a function_id (to determine which implementation to test your code with), and the target z.
• The judge will call your findSolution and compare your results with the answer key.
• If your results match the answer key, your solution will be Accepted.

Constraints:

• 1 <= function_id <= 9
• 1 <= z <= 100
• It is guaranteed that the solutions of f(x, y) == z will be in the range 1 <= x, y <= 1000.
• It is also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000.

예시

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: The hidden formula for function_id = 1 is f(x, y) = x + y.
The following positive integer values of x and y make f(x, y) equal to 5:
x=1, y=4 -> f(1, 4) = 1 + 4 = 5.
x=2, y=3 -> f(2, 3) = 2 + 3 = 5.
x=3, y=2 -> f(3, 2) = 3 + 2 = 5.
x=4, y=1 -> f(4, 1) = 4 + 1 = 5.

Example 2:

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: The hidden formula for function_id = 2 is f(x, y) = x * y.
The following positive integer values of x and y make f(x, y) equal to 5:
x=1, y=5 -> f(1, 5) = 1 * 5 = 5.
x=5, y=1 -> f(5, 1) = 5 * 1 = 5.

 

풀이

"""
   This is the custom function interface.
   You should not implement it, or speculate about its implementation
   class CustomFunction:
       # Returns f(x, y) for any given positive integers x and y.
       # Note that f(x, y) is increasing with respect to both x and y.
       # i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
       def f(self, x, y):
  
"""

from typing import Callable

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        ret = []
        
        def bsearch(known: int, goal: int, func: Callable, left: int, right: int, ret: list):
            if left == right:
                if func(known, left) == goal:
                    ret.append([known, left])
                
                return

            mid = int((left + right) / 2)
            mid_val = func(known, mid)

            if mid_val == z:
                ret.append([known, mid])
                return
            
            if mid_val < goal:
                return bsearch(known, goal, func, mid+1, right, ret)
            elif mid_val > goal:
                return bsearch(known, goal, func, left, mid-1, ret)

        for x in range(1, 1000):
            local_min = customfunction.f(x, 1)
            local_max = customfunction.f(x, 1000)
            
            if local_min > z:
                break

            if z < local_min or z > local_max:
                continue

            bsearch(x, z, customfunction.f, 1, 1000, ret)

        return ret

이런 형식의 문제는 처음 겪어봐서 뭘하라는 건지 한참 멍 때린 문제.

간략하게 문제를 설명하면 customfunction.f(x, y) == z를 만족하는 모든 (x, y)를 구하라 (1 <= x, y <= 1000) 이다.

 

1 <= x, y <= 1000 이므로 만들 수 있는 모든 조합인 백만 케이스 (1000 ** 2 == 1,000,000)를 모두 탐색하면 TLE가 난다.

(일반적으로 LeetCode에서 백만 케이스 실행 or O(n) = n ** 2를 TLE 기준으로 잡는 것 같다.)

 

모르는 방정식의 x, y를 대입을 통해서 구하라고하니 가장 먼저 생각나는 방식은 DL 알고리즘처럼 Newton's method가 였는데, 방정식 안의 미지수의 차수를 모르는 상태로 적용하려면 미친듯이 복잡해지므로 pass한다.

 

위의 방식은 loop를 돌면서 x를 정하고, y는 정해진 범위 [1, 1000]에서 binary search를 통해 발견한다.  binary search 시에 O(n) = log n 이고 n번 루프를 반복하므로 O(n) = n log n (실제로는 범위가 상수 1000으로 정해져있지만) 이 된다.

이렇게 풀이하면 beats 55%, 여기서 정말 작은 개선점으로 local_min > z: break로 early exit 해주면 beats 97%가 된다.

 

이외에도 처음에 말한 뉴튼 메소드 등 다른 방식이 있겠지만 점심 시간 밖에 시간이 없는 출근 요정이라 시간이 없으므로 20000~