[Python] 2485. Find the Pivot Integer

Find the Pivot Integer - LeetCode

 

문제 설명

n이 입력으로 주어질 때, 1 ~ x의 합과 x ~ n의 합이 같아지는 x를 구하는 문제.

조건을 만족하는 x가 없다면 -1을 리턴한다.

 

 

문제 풀이

(1) 사용한 알고리즘

이분탐색 (Binary Search)

 

(2) 시간복잡도

O(n * log n)

 

(3) 설명

[1, 2, 3, ..., n]까지의 리스트를 만들어, 이분탐색으로 x를 구해나간다.

현재 구한 x를 기준으로, 1 ~ x의 합과 x ~ n의 합을 각각 구해 값을 비교한다. 

• 만약 두 값이 같은 경우, 현재 x를 return 
• 1 ~ x의 합이 x ~ n의 합보다 작은 경우, x를 오른쪽 구간에서 이분 탐색 진행
• 1 ~ x의 합이 x ~ n의 합보다 큰 경우, x를 왼쪽 구간에서 이분 탐색 진행

 

(4) 풀이 코드

class Solution:
    def pivotInteger(self, n: int) -> int:
        nums = [i + 1 for i in range(n)]
        left, right = 0, n - 1

        while left <= right:
            mid = int((left + right) / 2)

            left_sum = sum(nums[:mid + 1])
            right_sum = sum(nums[mid:])

            if left_sum == right_sum:
                return mid + 1

            elif left_sum > right_sum:
                right = mid - 1

            else:
                left = mid + 1

        return -1