문제 이해하기
숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트를 먼저 정렬한 뒤 인접한 두 숫자 사이의 가장 큰 차이(간격)를 구하는 것이 목표입니다.
예를 들어 입력이 [5, 2, 3, 9, 10, 11]이라면 출력은 4가 됩니다. 리스트를 정렬하면 [2, 3, 5, 9, 10, 11]이 되는데, 이때 5와 9 사이의 간격인 4가 가장 크기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 주어진 리스트 nums를 오름차순으로 정렬합니다.
- 각 차이 값을 저장할 새로운 리스트를 준비합니다.
- 정렬된 리스트를 처음부터 끝까지 순회하며 인접한 두 요소의 차이(n[i+1] - n[i])를 계산해 저장합니다.
- 마지막으로 저장된 차이 값들 중 최댓값을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작 과정을 확인해 보겠습니다.
class Solution:
def solve(self, nums):
n = sorted(nums)
ans = []
for i in range(len(n)-1):
ans.append(n[i+1]-n[i])
return max(ans)
ob = Solution()
nums = [5, 2, 3, 9, 10, 11]
print(ob.solve(nums))
입력
[5, 2, 3, 9, 10, 11]
출력
4
시간 복잡도 분석
리스트 정렬에 O(n log n)의 시간이 소요되고, 인접 요소 간 차이를 계산하는 순회에는 O(n)이 걸립니다. 따라서 이 알고리즘의 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 차이 값을 저장하는 리스트 때문에 O(n)입니다.