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이 옵니다.
후속 질문
예를 들어 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로 바꿉니다. 값을 붙여 넣기 전에 정수로 변환하세요.
자주 묻는 질문3
Summary Ranges의 시간 복잡도는 얼마인가요?
O(n). 각 값은 한 번 방문하고, 각 범위는 한 번 기록합니다. 출력 목록을 제외하면 추가 공간은 O(1)입니다. 현재 범위의 시작점과 하나 또는 두 개의 인덱스만 사용합니다.
모든 간격에서 자르면 왜 범위의 개수가 가장 적을까요?
범위에는 연속된 정수가 들어 있으므로, 그 사이에 숫자가 빠진 두 값을 포함할 수 없습니다. 따라서 정렬된 배열의 모든 간격은 두 범위를 구분해야 하며, 간격이 g개라면 최소 g+1개의 범위가 필요합니다. 간격에서만 나누면 정확히 g+1개가 됩니다.
숫자가 하나만 있는 범위는 어떻게 처리하나요?
범위의 시작값과 끝값이 같은지 확인하세요. 같다면 "9"처럼 해당 값만 쓰세요. 같지 않다면 "5->6"처럼 시작값, 화살표, 끝값을 쓰세요. 두 개의 포인터를 사용하는 경우 조건은 i == j입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def summaryRanges(nums):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자
nums = [0, 1, 2, 5, 6, 9]
예상 출력
["0->2", "5->6", "9"]