파이썬으로 배열의 최댓값 인덱스 찾기 – compare()만 사용하는 이진 탐색 풀이

문제 정의

외부 클래스에서 직접 접근할 수 없는 비공개 배열을 담고 있는 TestArray 클래스가 하나 주어져 있습니다. 이 클래스는 오직 두 개의 공개 메서드만 제공합니다.

• length() – 배열의 길이를 반환합니다.
• compare(l, r, x, y) – 네 개의 인덱스를 인자로 받아 두 구간의 합을 비교한 결과를 반환합니다.

compare() 메서드의 동작 방식은 다음과 같습니다.

• (array[l] + array[l+1] + … + array[r]) > (array[x] + array[x+1] + … + array[y])이면 1을 반환
• 두 구간의 합이 서로 같으면 0을 반환
• (array[l] + array[l+1] + … + array[r]) < (array[x] + array[x+1] + … + array[y])이면 -1을 반환

즉, 우리가 해야 할 일은 배열 내부에 직접 접근하지 않고 이 두 메서드만 활용해 배열에서 최댓값이 위치한 인덱스를 찾아내는 것입니다.

예를 들어 입력 배열이 [8, 4, 2, 12, 11, 8, 4, 2, 7]이라면, 가장 큰 값은 12이고 이 값은 인덱스 3에 위치하므로 결과는 3이 됩니다.

접근 방식: 이진 탐색 활용

이 문제는 이진 탐색과 유사한 분할 정복 기법으로 해결할 수 있습니다. 탐색 범위를 절반씩 나눈 뒤 compare()로 양쪽 구간의 합을 비교하고, 합이 더 큰 쪽에 최댓값이 있을 가능성이 높다고 판단하여 탐색 범위를 계속 좁혀 나갑니다.

알고리즘의 구체적인 진행 순서는 다음과 같습니다.

1. n := length() 로 배열의 길이를 구합니다.
2. low := 0, high := n - 1 로 탐색 범위를 초기화합니다.
3. low < high 인 동안 아래 과정을 반복합니다.
   • mid := (low + high + 1) / 2 의 내림값
   • (low + high + 1) 이 짝수일 때:
     • res := compare(low, mid-1, mid, high)
     • res 가 1이면 high := mid - 1, 그렇지 않으면 low := mid
   • (low + high + 1) 이 홀수일 때:
     • res := compare(low, mid-1, mid+1, high)
     • res 가 1이면 high := mid - 1
     • res 가 -1이면 low := mid + 1
     • res 가 0이면 mid 를 그대로 반환
   • high 와 low 가 같아지면 high 를 반환합니다.
4. 반복문이 종료되면 -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

마무리

이 풀이는 배열의 요소를 하나씩 직접 조회하지 않고도 compare() 메서드의 비교 결과만으로 탐색 범위를 절반씩 줄여 나가기 때문에, 메서드 호출 횟수 기준으로 O(log n) 수준의 효율성을 기대할 수 있습니다. 배열에 대한 직접 접근이 차단된 환경에서도 공개 인터페이스만으로 원하는 정보를 추출해내는 대표적인 분할 정복 문제의 좋은 예시입니다.