정수 배열이 주어졌을 때, 가장 긴 연속된 요소 시퀀스의 길이를 구하는 문제를 살펴보겠습니다. 예를 들어 입력이 [100, 4, 250, 1, 3, 2]라면, 가장 긴 연속 시퀀스는 [1, 2, 3, 4]이므로 정답은 4가 됩니다.
문제 해결 접근 방식
이 문제의 핵심은 각 숫자가 연속 시퀀스의 시작점인지 판별하는 것입니다. 시작점이라는 것은 자신보다 1 작은 숫자(i-1)가 집합에 존재하지 않는 경우를 의미합니다. 이렇게 하면 불필요한 중복 탐색을 피할 수 있어 전체 시간 복잡도를 O(n)으로 유지할 수 있습니다.
해결 과정은 다음과 같습니다.
- 배열을 집합(set)으로 변환하고, longest 변수를 0으로 초기화합니다.
- 집합의 각 요소 i에 대해 다음을 검사합니다.
- i - 1이 집합에 없다면, i는 연속 시퀀스의 시작점입니다.
- current := i로 설정하고 streak(연속 길이)을 0으로 초기화한 뒤,
- i가 집합에 존재하는 동안 i와 streak을 계속 1씩 증가시킵니다.
- 매 반복마다 longest를 longest와 streak 중 더 큰 값으로 갱신합니다.
- 모든 순회가 끝나면 longest를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작 방식을 확인해 보겠습니다.
class Solution(object):
def longestConsecutive(self, a):
a = set(a)
longest = 0
for i in a:
if i-1 not in a:
current = i
streak = 0
while i in a:
i += 1
streak += 1
longest = max(longest, streak)
return longest
ob = Solution()
print(ob.longestConsecutive([100,4,250,1,3,2]))입력
[100,4,250,1,3,2]
출력
4
알고리즘 상세 설명
왜 집합(set)을 사용할까?
집합은 평균적으로 O(1)의 시간 복잡도로 멤버십 검사(존재 여부 확인)를 수행할 수 있습니다. 리스트를 그대로 사용하면 매번 O(n)의 검색 비용이 발생해 전체 성능이 크게 저하됩니다. 또한 집합은 중복 요소를 자동으로 제거하므로, 같은 숫자가 여러 번 등장해도 결과에 영향을 주지 않습니다.
시간 복잡도 분석
겉보기에는 이중 반복문(while 루프 포함) 때문에 O(n²)처럼 보일 수 있지만, 실제로는 그렇지 않습니다. while 루프는 오직 시퀀스의 시작점에서만 실행되며, 각 숫자는 최대 한 번만 방문되기 때문입니다. 따라서 전체 시간 복잡도는 O(n), 공간 복잡도는 집합 저장을 위해 O(n)입니다.
동작 과정 예시
입력 [100, 4, 250, 1, 3, 2]의 경우:
- 100 → 99가 없으므로 시작점. 101이 없어 길이 1
- 4 → 3이 존재하므로 건너뜀
- 250 → 249가 없으므로 시작점. 251이 없어 길이 1
- 1 → 0이 없으므로 시작점. 1→2→3→4까지 이어져 길이 4
- 3, 2 → 앞 숫자가 존재하므로 건너뜀
최종적으로 가장 긴 시퀀스 [1, 2, 3, 4]의 길이인 4가 반환됩니다.