Summary Ranges
서로 다른 정수로 이루어진 정렬된 배열 nums가 주어집니다. 모든 값이 정확히 하나의 범위에 속하도록 연속된 정수의 범위들을 가능한 한 적은 수로 나누세요. 범위 a..b는 텍스트 "a->b"로, 값이 하나인 경우에는 "a"로 나타내세요. 범위들을 오름차순으로 반환하세요.
함수
- numsinteger-array
- 정렬된 서로 다른 정수 배열
- 반환값string-array
- 범위를 텍스트로 표시하며, 가장 작은 값부터 가장 큰 값까지
제약 조건
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109nums는 오름차순으로 정렬되어 있으며 중복 항목이 없습니다.
예제
- 입력
- nums = [0, 1, 2, 5, 6, 9]
- 출력
- ["0->2", "5->6", "9"]
- 설명
0, 1, 2는 서로 연속되므로"0->2"를 이룹니다. 2에서 5로의 간격은 새로운 범위인"5->6"을 시작하고, 9는"9"로 단독으로 나타납니다.
- 입력
- nums = [-3, -1, 0, 1, 4, 7, 8]
- 출력
- ["-3", "-1->1", "4", "7->8"]
- 설명
- -3에는 이웃한 수가 없습니다(-2가 빠져 있음).
-1, 0, 1은 연속된 수열을 이루고, 4는 홀로 있으며,7, 8은 목록의 끝을 장식합니다. 음수도 같은 방식으로 작동합니다. -1 다음에는 -1 + 1 = 0이 옵니다.
제출 시 숨은 테스트 +16개
후속 질문
예를 들어 nums에 [1, 2, 2, 3]처럼 중복된 값이 들어 있을 수 있다고 가정해 보세요. 그래도 "1->3"이 출력되도록 하려면 무엇을 바꾸면 될까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
배열이 정렬되어 있습니다. 두 인접한 값이 같은 범위에 속하는 경우는 언제인가요?
nums[i+1] == nums[i] + 1일 때만 서로 같은 범위에 속합니다. 그 외의 모든 이웃한 쌍은 한 범위의 끝이자 다음 범위의 시작을 나타냅니다.현재 범위가 어디서 시작했는지 기억하세요. 다음 값이 현재 값보다 1 더 큰 동안 앞으로 이동하세요. 연속된 구간이 끊기거나 배열이 끝나면 시작 값부터 현재 값까지의 범위를 출력하고, 다음 값에서 새 범위를 시작하세요.
풀이
값이 정렬되어 있고 서로 다르므로, 연속된 정수의 범위는 항상 배열에서 서로 이웃한 값들의 연속 구간이며, 두 이웃한 값의 차이가 1보다 클 때 정확히 범위가 끝납니다. 이러한 간격마다 배열을 나누면 가능한 한 적은 수의 범위가 만들어집니다. 어떤 범위도 간격을 가로지를 수 없기 때문입니다. 이제 남은 것은 각 연속 구간의 시작과 마지막 요소, 그리고 텍스트 형식을 꼼꼼히 처리하는 일입니다.
모든 값의 양쪽 이웃을 확인하세요
핵심 아이디어
한 번에 값 하나씩 살펴보며 두 가지 질문을 해 보세요. 여기서 범위가 시작하나요? 네, 첫 번째 값이거나 이전 값이 1만큼 작지 않을 때입니다. 여기서 범위가 끝나나요? 네, 마지막 값이거나 다음 값이 1만큼 크지 않을 때입니다.
[0, 1, 2, 5, 6, 9]에서는 0, 5, 9에서 범위가 시작되고 2, 6, 9에서 끝납니다. 현재 범위가 시작된 값을 기억해 두세요. nums[i]에서 범위가 끝날 때 "start->nums[i]"를 작성하세요. 단, 9처럼 범위가 같은 값에서 시작하고 끝났다면 "start"만 작성하세요.
각 값을 한 번씩 방문하고 양옆의 값 두 개를 살펴보므로 시간 복잡도는 O(n)입니다. 출력 외에는 시작 값 하나만 기억하면 되므로 추가 공간 복잡도는 O(1)입니다.
알고리즘
start = nums[0]으로 설정합니다.- 각 인덱스
i에 대해:i > 0이고nums[i] != nums[i-1] + 1이면start = nums[i]로 설정합니다. i가 마지막 인덱스이거나nums[i+1] != nums[i] + 1이면 범위가 여기서 끝납니다.start == nums[i]이면"start"를, 그렇지 않으면"start->nums[i]"를 추가합니다.- 마지막 인덱스 이후에 목록을 반환합니다.
def summaryRanges(nums):
n = len(nums)
ranges = []
start = nums[0]
for i in range(n):
# A range opens where the value before is not one less.
if i > 0 and nums[i] != nums[i - 1] + 1:
start = nums[i]
# A range closes where the value after is not one more.
if i == n - 1 or nums[i + 1] != nums[i] + 1:
ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return ranges각 연속 구간을 훑는 두 포인터
핵심 아이디어
각 범위를 배열의 한 블록으로 보고 양 끝을 찾습니다. 포인터 i는 범위의 첫 번째 값에 위치합니다. 포인터 j는 i에서 시작해 다음 값이 정확히 1만큼 큰 동안 오른쪽으로 이동하므로, 범위의 마지막 값에서 멈춥니다.
[-3, -1, 0, 1, 4, 7, 8]의 경우: -3에 있는 i는 확장할 수 없습니다. -1은 -2가 아니므로 범위는 "-3"입니다. 그런 다음 i는 -1로 이동하고, j는 0과 1을 지나 4 앞에서 멈춥니다. 결과는 "-1->1"입니다. 이어서 "4"와 "7->8"이 나옵니다. 각 범위를 처리한 뒤 i는 다음 범위의 첫 번째 값인 j+1로 이동합니다.
범위의 개수는 가능한 한 적습니다. 간격이 있는 두 값은 절대로 같은 범위에 속할 수 없고, 이 방법은 간격이 있는 곳에서만 분할하기 때문입니다. 두 포인터는 모두 앞으로만 이동하므로, 모든 범위에 걸쳐 내부 루프는 총 n번 실행됩니다. 따라서 시간 복잡도는 O(n)이고 추가 공간 복잡도는 O(1)입니다.
알고리즘
i = 0으로 설정합니다.j = i로 설정하고,j+1 < n및nums[j+1] == nums[j] + 1인 동안j를 오른쪽으로 이동합니다.i == j이면"nums[i]"를 추가하고, 그렇지 않으면"nums[i]->nums[j]"를 추가합니다.i = j + 1로 설정하고i가 끝을 지날 때까지 반복합니다.- 목록을 반환합니다.
def summaryRanges(nums):
ranges = []
n = len(nums)
i = 0
while i < n:
# i is the first value of a run; push j to its last value.
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
# The next run starts right after this one.
i = j + 1
return ranges
함정과 경계 사례
로직은 몇 줄이면 충분하고, 실수는 가장자리에서 발생합니다.
- 마지막 범위를 빠뜨리는 경우. 간격을 만났을 때만 범위를 기록하는 루프는 마지막 범위를 기록하지 않으므로
[0, 1, 2, 5, 6, 9]에서"9"가 누락됩니다. 마지막 인덱스에서도 범위를 닫으세요. - 단일 값을
"a->a"로 쓰는 경우. 값이 하나인 범위는"a"로 씁니다. - 큰 값을 과학적 표기법으로 출력하는 경우. R은
1000000000과 같은 double을1e+09로 바꿉니다. 값을 붙여 넣기 전에 정수로 변환하세요.
자주 묻는 질문4
Summary Ranges의 시간 복잡도는 얼마인가요?
O(n). 각 값은 한 번 방문하고, 각 범위는 한 번 기록합니다. 출력 목록을 제외하면 추가 공간은 O(1)입니다. 현재 범위의 시작점과 하나 또는 두 개의 인덱스만 사용합니다.
모든 간격에서 자르면 왜 범위의 개수가 가장 적을까요?
범위에는 연속된 정수가 들어 있으므로, 그 사이에 숫자가 빠진 두 값을 포함할 수 없습니다. 따라서 정렬된 배열의 모든 간격은 두 범위를 구분해야 하며, 간격이 g개라면 최소 g+1개의 범위가 필요합니다. 간격에서만 나누면 정확히 g+1개가 됩니다.
숫자가 하나만 있는 범위는 어떻게 처리하나요?
범위의 시작값과 끝값이 같은지 확인하세요. 같다면 "9"처럼 해당 값만 쓰세요. 같지 않다면 "5->6"처럼 시작값, 화살표, 끝값을 쓰세요. 두 개의 포인터를 사용하는 경우 조건은 i == j입니다.
Summary Ranges에는 입력이 정렬되어 있어야 하나요?
네. 이 메서드는 이웃한 값만 비교하므로, 연속된 정수들이 서로 나란히 있어야 합니다. 정렬되지 않은 입력의 경우 먼저 정렬하면 전체 작업이 O(n log n)이 되며, 또는 최장 연속 수열 문제에서처럼 값을 해시 집합에 넣고 각 범위를 가장 작은 값부터 확장할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def summaryRanges(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
입력
nums = [0, 1, 2, 5, 6, 9]
기대값
["0->2", "5->6", "9"]