파이썬 알고리즘: 배열의 최댓값이 다른 모든 수의 두 배 이상인지 확인하기

문제 개요

정수 배열 nums가 주어졌다고 가정해 봅시다. 이 배열에는 항상 정확히 하나의 최댓값이 존재합니다. 우리가 확인해야 할 것은 이 최댓값이 배열 내 다른 모든 숫자보다 적어도 두 배 이상 큰지 여부입니다.

• 조건을 만족하면 → 최댓값의 인덱스를 반환합니다.
• 조건을 만족하지 않으면 → -1을 반환합니다.

예시

입력이 [3, 6, 1, 0]이라면 결과는 1입니다. 6이 배열의 최댓값이며, 나머지 숫자(3, 1, 0) 각각에 대해 6은 그 두 배보다 크기 때문입니다. 최댓값 6의 인덱스가 1이므로 반환값 역시 1이 됩니다.

풀이 접근 방법

이 문제는 다음 단계를 통해 손쉽게 해결할 수 있습니다.

1. maximum 변수에 배열 nums의 최댓값을 저장합니다.
2. 인덱스 i를 0부터 배열 길이까지 순회하며 다음을 검사합니다.
   • nums[i]가 maximum과 같다면, 해당 인덱스를 maxindex로 저장합니다.
   • nums[i]가 maximum과 다르면서 maximum < 2 * nums[i]라면, 최댓값이 그 수의 두 배 이상이 아니라는 의미이므로 즉시 -1을 반환합니다.
3. 반복문이 정상적으로 종료되면 저장해 둔 maxindex를 반환합니다.

파이썬 구현 코드

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

class Solution:
    def dominantIndex(self, nums):
        maximum = max(nums)
        for i in range(len(nums)):
            if nums[i] == maximum:
                maxindex = i
            if nums[i] != maximum and maximum < 2*(nums[i]):
                return -1
        return maxindex
ob = Solution()
print(ob.dominantIndex([3, 6, 1, 0]))

입력

[3, 6, 1, 0]

출력

1

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번 순회하며 최댓값 위치와 조건을 동시에 확인합니다.
• 공간 복잡도: O(1) — 추가 자료구조 없이 몇 개의 변수만 사용합니다.

마무리

이 문제의 핵심은 최댓값을 먼저 구한 뒤, 한 번의 순회만으로 '두 배 조건'을 검사할 수 있다는 점입니다. 조건 위반 시 조기 반환(early return)을 활용하면 불필요한 연산을 줄여 코드의 효율성과 가독성을 모두 높일 수 있습니다.