Longest Consecutive Sequence
특정한 순서가 아닌 정수 배열 nums가 주어집니다. 연속 수열은 x, x+1, x+2 등으로 이루어진 값들의 그룹이며, 각 값은 nums의 어딘가에 나타납니다. 가장 긴 연속 수열의 길이를 반환하세요. 두 번 이상 나타나는 값도 한 번만 셉니다.
함수
- numsinteger-array
- 정수, 순서는 상관없으며 반복 허용
- 반환값integer
- nums에 있는 연속된 값의 최장 연속 길이
제약 조건
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- 값은 반복될 수 있습니다. 배열에서의 위치는 중요하지 않으며, 어떤 값이 있는지만 중요합니다.
예제
- 입력
- nums = [40, 4, 39, 1, 3, 2, 41]
- 출력
- 4
- 설명
1,2,3및4가 모두 배열에 흩어져 있더라도 연속된 4개의 값으로 존재합니다. 다른 연속 구간인39부터41까지는 값이 3개뿐입니다.
- 입력
- nums = [7, 3, 7, 5, 6, 5]
- 출력
- 3
- 설명
5,6,7은 3개의 연속된 수를 이룹니다. 두 번째7과 두 번째5는 아무것도 더하지 않으며,4가 없으므로3은 합류할 수 없습니다.
- 입력
- nums = [10, 30, 20]
- 출력
- 1
- 설명
- 차이가 1인 값은 두 개도 없으므로, 각 구간에는 값이 하나씩만 들어 있고 정답은 1입니다.
후속 질문
값이 한 번에 하나씩 들어오고, 각 값이 들어올 때마다 지금까지의 가장 긴 연속 구간을 보고해야 한다고 가정해 보세요. 값마다 평균 O(1) 시간에 답을 최신 상태로 유지할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 값을 수열의 첫 번째 숫자로 시도하고 계속 세어 보세요. 어떤 질문을 반복해서 하게 되며, 배열에서 그 값을 찾을 때 답변 하나마다 비용이 얼마나 드나요?
질문은 "배열에
x+1이 있는가?"입니다. 해시 집합은 평균적으로 상수 시간에 답을 제공하며, 중복 항목도 제거합니다.x-1이 집합에 없는 값x에서만 세기를 시작합니다. 그 지점부터 집합에 값이 있는 동안x+1,x+2등으로 이동하고, 가장 긴 이동 경로를 유지합니다. 그러면 각 값은 하나의 이동 경로에서만 지나가게 됩니다.
풀이
연속된 값들은 배열 어디에나 있을 수 있습니다. 정렬하면 O(n log n) 시간에 값들을 순서대로 정렬할 수 있습니다. 해시 집합은 x+1이 있는지 O(1) 시간에 확인하고, x-1이 없는 값에서만 세기 시작하면 각 값을 한 번씩만 확인하므로 총 O(n) 시간입니다.
배열을 검색하여 각 값부터 세어 올라갑니다
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
모든 값을 연속 구간의 시작일 가능성이 있는 값으로 취급합니다. x에서 시작해 배열에서 x+1, 그다음 x+2를 검색하다가 값이 없으면 멈추고, 가장 긴 개수를 유지합니다. 모든 연속 구간에는 nums에서 가장 작은 값이 있으며, 루프는 그 값에서 시작해 전체 구간을 순회합니다.
각 검색은 최대 n개의 값을 읽으며, 긴 연속 구간은 각 원소에서 다시 순회됩니다. 섞인 하나의 연속 구간을 이루는 10^4개의 값에 대해 순회에는 약 n²/2 = 5 × 10^7단계가 걸리고, 각 단계는 평균적으로 배열의 절반을 검색하므로 비교 횟수는 약 2.5 × 10^11회입니다.
알고리즘
best를 0으로 설정합니다.nums의 각 값start에 대해current를start로,length를 1로 설정합니다.nums를 검색해current+1을 찾을 때까지current와length에 1을 더합니다.length가 더 크면 이를best에 저장합니다.best를 반환합니다.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return best정렬한 다음 연속 구간의 개수를 세세요
핵심 아이디어
정렬하면 각 연속 구간의 값들이 서로 옆에 놓입니다. [40, 4, 39, 1, 3, 2, 41]은 [1, 2, 3, 4, 39, 40, 41]이 되며, 연속 구간은 왼쪽에서 오른쪽으로 읽어 냅니다.
정렬된 값들을 순회하면서 현재 연속 구간의 길이를 유지합니다. 이전 값보다 1 큰 값은 구간을 연장합니다. 같은 값이 반복되면 구간을 연장하지도 끝내지도 않으므로 건너뜁니다. 그 외의 값은 길이가 1인 새 구간을 시작합니다.
정렬에는 O(n log n)이, 순회에는 O(n)이 듭니다. 제자리 정렬은 추가 배열이 필요하지 않습니다. 복사본을 정렬하는 언어에서는 메모리 O(n)이 필요합니다.
알고리즘
nums를 오름차순으로 정렬합니다.- 배열은 비어 있지 않으므로
best와run을 1로 설정합니다. - 1부터 각 인덱스
i에 대해,nums[i]가nums[i-1]와 같으면 건너뜁니다. nums[i]가nums[i-1]+1이면run에 1을 더하고, 그렇지 않으면run을 1로 설정합니다.run이 더 크면best에 저장합니다.best를 반환합니다.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return best각 실행의 시작부터만 세는 해시 집합
핵심 아이디어
해시 집합의 각 값에 대해 멤버십 확인은 평균적으로 O(1)의 비용이 들며, 중복된 값은 하나의 항목으로 합쳐집니다.
모든 값에서 시작해 걸으면 작업이 여전히 반복됩니다. 1, 2, 3, 4가 있는 경우 1에서 3번, 2에서 2번, 3에서 1번 이동하게 됩니다. 따라서 연속 구간의 첫 번째 값에서만 이동해야 합니다. 이는 정확히 x-1이 없는 값 x입니다. 예제 1에서는 1과 39만 이에 해당하므로, 길이가 각각 4와 3인 연속 구간이 만들어집니다.
모든 값은 하나의 연속 구간에 속하고 해당 구간의 이동에서만 방문되므로, 모든 이동을 합쳐도 최대 n번입니다. 값마다 한 번씩 확인하므로 전체 시간 복잡도는 O(n)이고, 집합에 필요한 메모리는 O(n)입니다.
알고리즘
nums의 모든 값을 해시 집합values에 넣고,best를 0으로 설정합니다.- 집합의 각 값
x에 대해,x-1이 집합에 있으면 건너뜁니다. 해당 값은 연속 구간의 첫 번째 값이 아닙니다. - 그렇지 않으면
end를x로 설정하고,end+1이 집합에 있는 동안end에 1을 더합니다. end-x+1이 더 크면 이를best에 저장합니다.best를 반환합니다.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
함정과 경계 사례
- 정렬 후 중복 값을 간격이나 단계로 취급하는 경우입니다.
[1, 2, 2, 3]에서 두 번째2에서 연속 구간을 다시 시작하면 답은 2가 되고, 이를 단계로 세면 4가 됩니다. 정답은 3입니다. - 정렬된 순회에서
best를 0으로 시작하고 루프 안에서만 갱신하는 경우입니다. 그러면 값이 하나인 배열은 1 대신 0을 반환합니다. - 연속 구간의 시작점에서만 순회하지 않고 집합의 모든 값에서 순회하는 경우입니다. 그러면 값이
10^4개인 연속 구간 하나를 처리하는 데5 × 10^7단계가 걸립니다. - 집합이 아니라
nums를 순회하는 경우입니다. 길이 2,500인 연속 구간의 첫 값이 2,000번 나타나면, 해당 구간을 2,000번 순회하게 됩니다. - 값을 인덱스로 사용해 배열에 접근하는 경우입니다. 값의 범위가
±10^9에 이르므로2 × 10^9개의 항목이 필요합니다.
자주 묻는 질문3
가장 긴 연속 수열의 시간 복잡도는 얼마인가요?
해시 집합 풀이의 평균 시간 복잡도는 O(n)이고 추가 메모리 복잡도는 O(n)입니다. 정렬하고 연속 구간의 길이를 세는 데는 O(n log n)이 걸립니다. 집합 없이 다음 값이 있는지 배열을 검색하면 최대 O(n³)이 걸립니다.
추가 메모리 없이 가장 긴 연속 수열 문제를 풀 수 있나요?
네, 입력을 재정렬해도 된다면 제자리에서 정렬한 다음 한 번 순회하며 반복되는 값은 건너뛰고 연속된 값의 개수를 세면 됩니다. 이 방법은 추가 메모리를 O(1)만 사용하지만 시간은 O(n log n)이 걸립니다. O(n) 해법에는 해시 집합이 필요합니다.
유니온 파인드로 가장 긴 연속 수열 문제를 해결할 수 있을까요?
네. 서로 다른 각 값을 집합으로 만들고, 둘 다 존재할 때마다 x와 x+1을 합친 다음 가장 큰 집합의 크기를 반환하세요. 실행 시간은 거의 O(n)이지만, 값에서 인덱스로의 매핑과 부모 링크 및 크기가 필요합니다. 해시 집합 순회에는 집합 하나만 필요합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def longestConsecutive(nums):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
nums = [40, 4, 39, 1, 3, 2, 41]
예상 출력
4