[Leetcode 아주 상세한 문제풀이] 128. Longest Consecutive Sequence – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 128번 문제 Longest Consecutive Sequence 다.

우선 문제를 살펴보자.

 

리트코드 128번 문제 Longest Consecutive Sequence 링크

Longest Consecutive Sequence - LeetCode

Longest Consecutive Sequence - LeetCode

 

 

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.

Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
 
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 정렬되지 않은 정수 배열이 주어진다. 이때 주어진 정수 배열 중 연속되는 element들 중 길이가 가장 긴 배열의 길이를 리턴하라는 문제다.

문제 예시 1번을 살펴보면 인풋으로 [100,4,200,1,3,2] 라는 배열이 주어졌다. 이때 연속되는 배열은 1, 2, 3, 4로 이때 그 배열의 길이는 4이기 때문에 4를 리턴하면 된다. 참고로 consecutive라는 말은 연속된다는 뜻이지 오름차순이라는 뜻이 아니므로 혼동하지 말자.

문제 예시 2번을 살펴보면 인풋으로 [0,3,7,2,5,8,4,6,0,1] 라는 배열이 주어졌다. 이때 연속되는 배열은 0, 1, 2, 3, 4, 5, 6, 7, 8이다. 따라서 이때 연속되는 배열의 길이는 9이기 때문에 9를 리턴하면 된다. 유의할 점은 인풋 배열에서 0이 2번 주어졌지만 1번만 카운트 해야 한다는 점이다.

미지막으로 문제에서 요구하는 중요한 요건 중 하나는 O(n)의 time complexity를 갖는 알고리즘을 짜야 한다는 것이다. 문제 자체를 이해하기 어렵지 않기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 hash set을 이용할 것이다.

Hash set을 이용하면 해당 element들이 연속된 숫자인지 아닌지 빨리 확인할 수 있다.

구체적으로 다음과 같은 과정을 이용해 문제를 해결할 것이다.

1) 인풋으로 주어진 배열의 모든 element를 hash set에 넣는다.

2) 우리는 각 element들을 하나씩 탐색하는데 이때 그 element가 연속되는 숫자들의 '첫번째'인지 확인한다.

첫번째 element 확인은 직전 element와 차이가 1이 아닌 경우에 해당한다.

3) 만약 연속되는 숫자들의 '첫번째' element를 찾았다면 그것을 기점으로 그 다음 element 들을 차례로 탐색한다. 이때 차례대로 1씩 커지는지 확인한다.

4) 이 탐색을 하는 와중에 가장 긴 연속된 element의 길이를 업데이트 하고 모든 탐색을 마친 후 그 값을 리턴한다.

 

Time complexity

사실 이 문제를 손쉽게 해결하는 방법은 오름차순 정렬을 먼저 하는 것이다.

하지만 정렬을 한다는 것은 O (n log n)이라는 time complexity를 갖는다.

따라서 이는 문제에서 요구하는 바와 부합하지 않는다.

이런 점에서 hash set은 몇 가지 장점을 제공한다.

우선 주어진 배열을 hash set에 넣는데 O (n)의 time complexity가 필요하다.

그 후 hash set을 탐색하는 것 역시 O (n)의 time complexity가 필요하다.

따라서 전체적으로 O (n)의 time complexity가 필요하다.

더불어 set 함수의 경우 중복을 없애주는 역할도 한다.

Hash set의 특징은 리스트 배열처럼 인덱스를 이용하지 않고 특정 값이 존재하는지 아닌지 빨리 확인할 수 있다는 점이다.

이런 점에서 시작 element를 기준으로 연속되는 element (시작 element + 1)이 존재하는지 아닌지 빨리 확인이 가능하다.

따라서 O (n)의 time complexity로 이 문제를 해결하는데 hash set이 적절하다고 할 수 있다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

정수 배열을 입력받기 위한 함수를 정의해 준다. (line 1)

만약 함수가 비어있다면 연속되는 element들을 찾을 일도 없으므로 0을 리턴하고 종료한다. (line 2-3)

주어진 배열을 hash set에 넣어준다. (line 5)

그리고 연속되는 element들의 최대 길이를 저장해둘 변수를 하나 만들어 준다. (line 6)

이제 주어진 배열에서 element를 하나씩 탐색할 것이다. (line 8)

먼저 탐색하는 element가 연속되는 배열의 시작점인지 확인한다. (line 10)

위에서 설명했듯이 탐색하는 element에서 1을 뺀 것이 hash set에 있는지 없는지 확인한다.

만약 존재하지 않는다면 현재 탐색하고 있는 element가 연속되는 배열의 시작점이 될 수 있다.

따라서 현재 탐색하는 element를 시작점으로 잡고 문자 개수를 1개 카운트 해준다. (line 11-12)

이제 그 시작점을 기준으로 연속되는 element들이 있는지 탐색할 것이다.

시작점에서 1을 더한 값을 갖는 element가 hash set에 있는지 확인한다. (line 15)

만약 그것이 존재한다면 탐색 기준점을 그 element오 업데이트 해주고 동시에 문자 개수도 1개 더 카운트 해준다. (line 16-17)

이 과정은 연속되는 element가 존재하는한 while loop에서 계속 돌아가게 된다.

While loop가 멈춘다는 것은 연속되지 않는 element를 만났다는 뜻이다.

따라서 그때까지 탐색한 연속된 element들의 길이와 global하게 tracking하고 있는 연속되는 element 최대 길이를 서로 비교하여 더 큰 값을 취해 업데이트 한다. (line 19)

이 과정을 인풋으로 주어진 모든 배열에 대해 마치고 나면 최종적으로 global하게 tracking 하고 있던 연속되는 element들의 최대 길이를 리턴하고 종료한다. (line 21)

 

 

문제 풀이 코드

def longest_consecutive(nums):
    if not nums:
        return 0
 
    num_set = set(nums)
    max_length = 0
 
    for num in nums:
        # Check if it's the start of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_length = 1
 
            # Check for consecutive elements
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1
 
            max_length = max(max_length, current_length)
 
    return max_length
 
# Test the function with the provided examples
print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # Output: 4
print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  # Output: 9
 

 

 

관련 문제

리트코드 200번 Number of islands 문제 풀이 (링크)

리트코드 207번 Course schedule 문제 풀이 (링크)

 

128. Longest Consecutive Sequence