중복되지 않는 숫자로 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 이때 우리가 해야 할 일은, 리스트 안에서 서로 연속된 숫자들을 하나의 포괄적 구간(inclusive interval)으로 요약한 2차원 행렬을 정렬된 형태로 만드는 것입니다.
문제 이해하기
예를 들어 입력이 다음과 같다고 해봅시다.
nums = [10, 11, 12, 15, 16, 17, 28, 30]
그렇다면 출력은 아래와 같습니다.
[[10, 12], [15, 17], [28, 28], [30, 30]]
리스트에서 10부터 12까지, 그리고 15부터 17까지는 각각 연속된 숫자들이므로 하나의 구간으로 묶입니다. 반면 28과 30은 앞뒤 숫자와 이어지지 않으므로 [28, 28]과 [30, 30]처럼 단일 숫자 구간으로 표현됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 먼저 리스트
nums를 오름차순으로 정렬합니다. - 리스트의 끝에 무한대 값(예: 1e9)을 추가하여 마지막 구간도 처리할 수 있게 합니다.
- 결과를 담을 빈 리스트
ans를 생성합니다. - 구간의 시작점을 나타내는 변수
l을 첫 번째 원소로 초기화합니다. - 인덱스 1부터 리스트 끝까지 반복하면서, 현재 원소가 이전 원소 + 1과 같지 않다면(즉, 연속성이 끊긴다면)
[l, nums[i-1]]을 결과에 추가하고 새로운 시작점l을 현재 원소로 갱신합니다. - 모든 반복이 끝나면
ans를 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, nums):
nums.sort()
nums.append(1e9)
ans = []
l = nums[0]
for i in range(1, len(nums)):
if nums[i] != nums[i-1] + 1:
ans.append([l, nums[i-1]])
l = nums[i]
return ans
ob = Solution()
nums = [10, 11, 12, 15, 16, 17, 28, 30]
print(ob.solve(nums))입력
[10, 11, 12, 15, 16, 17, 28, 30]
출력
[[10, 12], [15, 17], [28, 28], [30, 30]]
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 정렬 과정이 지배적이므로 O(n log n)입니다. 정렬이 이미 완료된 입력이라면 선형 탐색만 수행하므로 O(n)의 시간 복잡도로 처리할 수 있습니다. 공간 복잡도는 결과 리스트를 제외하면 추가 메모리가 거의 필요하지 않아 O(1) 수준입니다.