정렬되지 않은 숫자 배열 nums가 주어졌을 때, 이 배열의 요소들이 서로 연속된 값(연속한 정수 나열)으로 이루어져 있는지 확인하는 문제를 생각해 볼 수 있습니다. 이때 음수도 함께 처리할 수 있어야 합니다.
예를 들어 입력이 nums = [-3, 5, 1, -2, -1, 0, 2, 4, 3]이라면, 요소들을 정렬했을 때 -3, -2, -1, 0, 1, 2, 3, 4, 5처럼 끊김 없이 이어지므로 결과는 True가 됩니다.
접근 방법
배열을 정렬하지 않고도, 다음 성질을 이용하면 문제를 해결할 수 있습니다.
- 요소들이 실제로 연속적이라면, 배열의 최솟값을 시작으로 하는 길이 n짜리 등차수열(공차 1)과 일치해야 합니다.
- 등차수열의 합 공식을 사용하면 기대되는 총합을 미리 계산할 수 있습니다.
- 기대합과 배열의 실제 총합이 같다면 연속적이라고 판단합니다.
구체적인 절차는 다음과 같습니다.
- size := 배열 nums의 크기
- init_term := 무한대(inf)로 초기화
- i를 0부터 size까지 반복하며
- nums[i]가 init_term보다 작으면 init_term := nums[i]로 갱신 (즉, 최솟값 탐색)
- ap_sum := 등차수열 합 공식으로 계산한 기대합 ((size * (2 * init_term + (size - 1) * 1)) / 2의 몫)
- total := nums의 모든 요소의 합
- ap_sum과 total이 같으면 true, 아니면 false 반환
이 방법은 최솟값을 한 번 찾고 합계를 한 번 구하는 것만으로 해결되므로, 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)입니다.
구현 예시
def solve(nums):
size = len(nums)
init_term = 999999
for i in range(size):
if nums[i] < init_term:
init_term = nums[i]
ap_sum = (size * (2 * init_term + (size - 1) * 1)) // 2
total = sum(nums)
return ap_sum == total
nums = [-3, 5, 1, -2, -1, 0, 2, 4, 3]
print(solve(nums))입력
[-3, 5, 1, -2, -1, 0, 2, 4, 3]
출력
True
참고: 주의할 점
이 방법은 합계만 비교하기 때문에, 중복 요소가 있는 경우 드물게 오답이 나올 수 있습니다. 예를 들어 [0, 0, 3]은 기대합(0+1+2=3)과 실제 합(3)이 같아 true로 판정되지만 실제로는 연속적이지 않습니다. 따라서 중복이 없음이 보장된 입력에서 가장 안전하게 동작하며, 중복 검사가 필요하다면 집합(set)을 활용해 요소 개수와 종류 개수를 함께 비교하는 보조 로직을 추가하는 것이 좋습니다.