숫자로 이루어진 리스트가 주어졌을 때, 가장 큰 수가 두 번째로 큰 수의 두 배보다 큰지 판별하는 문제를 살펴보겠습니다.
예를 들어 리스트가 [3, 9, 6]이라면 최댓값은 9이고, 두 번째로 큰 값 6의 두 배는 12입니다. 9는 12보다 작으므로 결과는 False가 됩니다. 반면 리스트가 [6, 3, 15]라면 최댓값 15는 12보다 크므로 결과는 True가 됩니다.
문제 접근 방법
이 문제는 리스트를 한 번만 순회하면서 최댓값(c_max)과 두 번째로 큰 값(p_max)을 동시에 추적하면 선형 시간 O(n) 안에 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- 리스트의 길이가 2 미만이면 비교 자체가 불가능하므로
False를 반환합니다. - 첫 두 원소를 이용해
p_max(두 값 중 작은 값)와c_max(두 값 중 큰 값)를 초기화합니다. - 세 번째 원소부터 마지막 원소까지 순회하면서 다음 규칙을 적용합니다.
- 현재 값이
c_max보다 크면: 기존c_max를p_max로 내리고 현재 값을 새로운c_max로 지정합니다. - 현재 값이
p_max보다 크고c_max보다 작거나 같으면: 현재 값을 새로운p_max로 지정합니다.
- 현재 값이
- 순회가 끝나면
c_max > p_max * 2여부를 반환합니다.
구현 예제
class Solution:
def solve(self, nums):
if len(nums) < 2:
return False
p_max = min(nums[0], nums[1])
c_max = max(nums[0], nums[1])
for i in range(2, len(nums)):
if nums[i] > p_max:
if nums[i] > c_max:
p_max = c_max
c_max = nums[i]
else:
p_max = nums[i]
return c_max > p_max * 2
ob = Solution()
nums = [3, 6, 15]
print(ob.solve(nums))
입력 및 출력
입력: [3, 6, 15]
출력: True
위 예제에서 최댓값은 15이고 두 번째로 큰 값은 6입니다. 6의 두 배인 12보다 15가 크므로 True가 출력됩니다.
더 간단한 방법: 정렬 활용하기
코드의 간결함이 성능보다 중요하다면 정렬을 이용해 훨씬 짧게 작성할 수도 있습니다.
def solve(nums):
if len(nums) < 2:
return False
largest, second = sorted(nums)[-2:]
return largest > second * 2
print(solve([3, 6, 15])) # True
print(solve([3, 9, 6])) # False
내장 모듈 heapq의 nlargest 함수를 사용하면 상위 두 개의 값만 추출해 더 효율적으로 처리할 수도 있습니다.
import heapq
def solve(nums):
if len(nums) < 2:
return False
largest, second = heapq.nlargest(2, nums)
return largest > second * 2
시간 복잡도 비교
- 단일 순회 방식: 시간 복잡도 O(n), 공간 복잡도 O(1)로 대용량 데이터에 가장 효율적입니다.
- 정렬 방식: 시간 복잡도 O(n log n)으로 코드는 간결하지만 데이터가 클수록 느려집니다.
실무에서는 데이터 크기와 코드 가독성 사이의 균형을 고려해 적절한 방식을 선택하면 됩니다.