다른 클래스에서 액세스할 수 없는 배열을 포함하는 'TestArray'라는 클래스와 두 개의 공개 멤버 함수 length() 및 compare()가 있다고 가정합니다. length() 함수는 배열의 길이를 반환하고 compare() 함수는 배열의 다양한 하위 배열을 비교하는 세 가지 다른 값을 반환합니다. 이 함수는 4개의 값 l, r, x, y를 입력으로 사용하고 다음과 같이 작동합니다. -
-
if (배열[l] + 배열[l+1]+......+배열[r-1]+배열[r])> (배열[x] + 배열[x+1]+... ...+배열[y1]+배열[y]); 1을 반환합니다.
-
if (배열[l] + 배열[l+1]+......+배열[r-1]+배열[r]) =(배열[x] + 배열[x+1]+... ...+배열[y1]+배열[y]); 0을 반환합니다.
-
if (배열[l] + 배열[l+1]+......+배열[r-1]+배열[r]) <(배열[x] + 배열[x+1]+... ...+배열[y1]+배열[y]); -1을 반환합니다.
배열 자체에 접근하지 않고 클래스의 멤버 함수만 사용하여 배열의 최대 요소 인덱스를 찾아야 합니다.
따라서 입력이 array =[8, 4, 2, 12, 11, 8, 4, 2, 7]과 같으면 출력은 3이 됩니다. 배열에서 가장 큰 요소는 12이고 인덱스에 위치합니다. 3.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=길이()
-
낮음:=0
-
높음 :=n - 1
-
낮은 동안 <높은, 수행
-
mid :=(low+high+1) / 2의 하한값
-
(low+high+1) mod 2가 0과 같으면
-
res :=비교(낮음, 중간-1, 중간, 높음)
-
res가 1과 같으면
-
높음 :=중간 -1
-
-
그렇지 않으면
-
낮음 :=중간
-
-
-
그렇지 않으면
-
res :=비교(낮음, 중간-1, 중간+1, 높음)
-
res가 1과 같으면
-
높음 :=중간 -1
-
-
그렇지 않으면 res가 -1과 같을 때
-
낮음 :=중간 -1
-
-
그렇지 않으면
-
중간 반환
-
-
-
높음이 낮음과 같으면
-
높은 수익
-
-
-
반환 -1
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class TestArray: def __init__(self, array) -> None: self.__arr = array def length(self): return len(self.__arr) def compare(self, l, r, x, y): val1 = sum(i for i in self.__arr[l:r+1]) val2 = sum(j for j in self.__arr[x:y+1]) if val1 > val2: return 1 elif val1 == val2: return 0 elif val1 < val2: return -1 def solve(reader): n = reader.length() low,high = 0,n - 1 while low < high: mid = (low+high+1)//2 if (low+high+1)%2 == 0: res = reader.compare(low,mid-1,mid,high) if res == 1:high = mid - 1 else:low = mid else: res = reader.compare(low,mid-1,mid+1,high) if res == 1:high = mid - 1 elif res == -1:low = mid + 1 else: return mid if high == low: return high return -1 arr_ob = TestArray([8, 4, 2, 12, 11, 8, 4, 2, 7]) print(solve(arr_ob))
입력
[8, 4, 2, 12, 11, 8, 4, 2, 7]
출력
3