Longest Consecutive Sequence
정수 배열 nums를 순서에 상관없이 받습니다. 연속 수열은 nums 어딘가에 각각 나타나는 x, x+1, x+2 등의 값들로 이루어진 그룹입니다. 가장 긴 연속 수열의 길이를 반환하세요. 두 번 이상 나타나는 값은 한 번만 셉니다.
함수
- 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입니다.
제출 시 숨은 테스트 +17개
후속 질문
값이 하나씩 들어오고, 각 값이 들어올 때마다 지금까지의 가장 긴 연속 구간을 알려줘야 한다고 가정해 보세요. 값마다 평균 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를 찾습니다. 값이 없을 때까지 계속 진행합니다. 도달한 값의 개수가 x에서 시작하는 연속 구간의 길이이며, 이 길이들 중 가장 큰 값이 답입니다.
모든 연속 구간에는 가장 작은 값이 있고, 그 값은 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부터 4까지 이어진 뒤 39로 건너뜁니다.
정렬된 값을 순회하며 현재 연속 구간의 길이를 유지합니다. 이전 값보다 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각 실행의 시작부터만 계산하는 해시 집합
핵심 아이디어
모든 값을 해시 집합에 넣으세요. 그러면 " x+1이 있는가?"를 확인하는 데 스캔하는 대신 평균적으로 O(1)의 시간이 걸리고, 중복 값은 하나의 항목으로 합쳐집니다.
모든 값에서 시작해 순회하면 여전히 작업이 반복됩니다. 1, 2, 3, 4의 연속 구간에서 1부터 3단계, 2부터 2단계, 3부터 1단계를 이동하게 됩니다. 따라서 연속 구간의 첫 번째 값에서만 순회를 시작하세요. 값 x는 x-1이 집합에 없을 때만 첫 번째 값입니다. [40, 4, 39, 1, 3, 2, 41]에서는 1과 39만 해당합니다. 1부터는 4에 도달하므로 길이는 4이고, 39부터는 41에 도달하므로 길이는 3입니다.
모든 값은 정확히 하나의 연속 구간에 속하며, 해당 구간의 첫 번째 값에서 시작하는 순회만 그 값을 지나가므로 모든 순회를 합해도 최대 n단계입니다. 값마다 멤버십 확인을 한 번 하고 집합을 만드는 작업을 더하면, 집합에 O(n)의 메모리를 사용하면서 총 시간은 O(n)입니다.
nums가 아니라 집합을 순회하세요. 2,500개 값으로 이루어진 연속 구간의 첫 번째 값이 nums에 2,000번 나타난다면, nums를 순회할 때 해당 구간을 2,000번 순회하게 됩니다.
알고리즘
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를 순회하는 경우입니다. 수천 번 나타나는 값에서 시작하는 연속 구간을 수천 번 탐색하게 됩니다. - 값을 인덱스로 사용하는 배열에 값을 표시하는 경우입니다. 값의 범위가
±10^9에 이르므로 배열에2 × 10^9개의 항목이 필요합니다.
자주 묻는 질문4
Longest Consecutive Sequence의 시간 복잡도는 얼마인가요?
해시 집합 솔루션은 평균적으로 O(n) 시간이 걸리고 O(n)의 추가 메모리를 사용합니다. 정렬한 다음 연속된 값의 개수를 세는 데는 O(n log n) 시간이 걸립니다. 집합 없이 다음 값이 있는지 배열을 검색하면 최대 O(n³) 시간이 걸립니다.
해시 집합을 사용하는 풀이에 for 루프 안에 while 루프가 있는데도 왜 O(n)인가요?
내부 루프는 왼쪽 이웃인 x-1이 없는 값, 즉 해당 연속 구간의 첫 번째 값부터만 실행됩니다. 각 값은 자신이 속한 연속 구간의 순회에서만 한 번씩 방문되며 다른 순회에서는 방문되지 않으므로, 모든 내부 루프의 총 단계 수는 최대 n입니다. 외부 루프는 각 값마다 확인을 한 번씩 추가하므로, 전체 시간 복잡도는 O(n)입니다.
추가 메모리 없이 가장 긴 연속 수열 문제를 풀 수 있나요?
네, 입력을 재정렬해도 된다면 제자리에서 정렬한 뒤 반복을 건너뛰면서 한 번 순회해 연속 구간을 세면 됩니다. 이 방법은 추가 메모리를 O(1) 사용하지만 시간은 O(n log n) 걸립니다. O(n) 해법에는 해시 집합이 필요합니다.
union-find로 최장 연속 수열 문제를 풀 수 있을까요?
네. 서로 다른 각 값을 집합으로 만들고, x와 x+1이 모두 있으면 이들을 합친 다음, 가장 큰 집합의 크기를 반환하세요. 실행 시간은 거의 O(n)이지만, 값에서 인덱스로의 매핑, 부모 링크와 크기가 필요합니다. 반면 해시 집합 순회는 집합 하나와 반복문 두 개로 같은 작업을 수행합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def longestConsecutive(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [40, 4, 39, 1, 3, 2, 41]
기대값
4