Python으로 배열에 중복을 허용하는 연속된 정수가 포함되어 있는지 확인하는 방법

숫자 배열 nums가 주어졌다고 가정해 보겠습니다. 이 배열에는 중복된 요소가 포함될 수 있습니다. 우리의 목표는 이 배열의 요소들이 연속된(contiguous) 숫자 집합을 이루고 있는지 확인하는 것입니다.

예를 들어, 입력이 다음과 같다면:

nums = [6, 8, 8, 3, 3, 3, 5, 4, 4, 7]

배열의 고유한 요소들은 3, 4, 5, 6, 7, 8로 끊김 없이 이어지므로 출력은 True가 됩니다.

문제 해결 접근 방식

이 문제는 다음 단계를 통해 간단하게 해결할 수 있습니다:

• 리스트 nums를 오름차순으로 정렬합니다.
• 인덱스 1부터 마지막 요소까지 반복하면서 인접한 두 요소의 차이를 검사합니다.
• nums[i] - nums[i-1] > 1인 경우가 하나라도 있다면, 숫자 사이에 빈틈이 존재한다는 의미이므로 False를 반환합니다.
• 모든 인접 요소의 차이가 1 이하라면(중복 허용), True를 반환합니다.

핵심 아이디어는 정렬 후 인접 요소 간 차이가 항상 0(중복) 또는 1(연속)이면 연속된 집합이라고 판단하는 것입니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다:

def solve(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] - nums[i-1] > 1:
            return False
    return True

nums = [6, 8, 8, 3, 3, 3, 5, 4, 4, 7]
print(solve(nums))

입력

[6, 8, 8, 3, 3, 3, 5, 4, 4, 7]

출력

True

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 정렬 과정이 지배적이므로 O(n log n)입니다. 공간 복잡도는 제자리(in-place) 정렬을 사용하므로 O(1)입니다.

만약 더 빠른 속도가 필요하다면, 집합(set)을 활용해 최솟값과 최댓값의 차이가 고유 요소 개수와 같은지 확인하는 O(n) 방법도 고려할 수 있습니다.