128. Longest Consecutive Sequence

Longest Consecutive Sequence - LeetCode

정수가 포함된 List가 주어진다.

이 List의 정수들이 연속되게 증가, 혹은 감소하는 조합의 최대 길이를 반환하는 문제다. 시간 복잡도 제한은 O(n)이다.

예시는 다음과 같다.

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.

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

1. 인덱스를 사용해서 체크하는 방법

from typing import *


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        check = [0] * 200002
        for num in nums:
            check[num + 100001] = 1
        result = 0
        temp = 0
        for i in range(len(check)):
            if check[i]:
                if temp == 0:
                    temp = 1
                else:
                    temp += 1
            else:
                temp = 0
            result = max(result, temp)
        return result

큰 정수 배열을 준비하고 주어진 nums를 선형 탐색하면서 정수가 있는지 빈도를 체크한다.

그리고 체크한 정수 배열을 선형 탐색하면서 연속적으로 체크된 가장 큰 길이를 반환하는 로직이다.

여기서 음수도 연속한 정수의 배열에 들어갈 수 있기 때문에 배열 사이즈를 2배로 늘리고, 절반인 100001을 더해서 해결하려고 했는데...

 

우선 조건에서 등장하는 정수의 범위는 -(10의 9승) ~ (10의 9승)까지다. 조건을 착각해버렸다...

게디가 주어진 범위는 단순히 하나의 배열로 할당할 수 없는 사이즈다.

설령 저 엄청 큰 배열을 선언할 수 있다 하더라도 저 배열을 선형 탐색하면 TLE가 발생한다.

 

2. Greedy 한 선형 탐색(?)

from typing import *


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        set1, checked = set(), set()
        for num in nums:
            set1.add(num)
        answer = 0
        for num in nums:
            if num not in checked:
                temp = 1
                checked.add(num)
                cur = num
                while cur + 1 in set1:
                    temp += 1
                    cur += 1
                    checked.add(cur)
                cur = num
                while cur - 1 in set1:
                    temp += 1
                    cur -= 1
                    checked.add(cur)
                answer = max(answer, temp)
        return answer

아무튼 상수 시간 복잡도로 해결을 해야 하니 Greedy 하게 접근해봤다.

우선 nums를 탐색하면서 num을 집합에 넣는다. 이러면 num이 있는지 유무는 O(1) 시간으로 알 수 있다.

이후에 다시 nums를 순회하면서 해당 num의 +1, -1 방향으로 연속된 값이 있었는지 체크하고 있다면 방문처리를 해주면서 현재까지 연속된 길이를 저장하고, 최종 결괏값을 업데이트하는 것을 반복한다.

 

방문처리를 해주기 때문에 중복된 길이를 찾지 않는다. 예를 들어서 [1,2,3,4]가 있다면 1에서 2,3,4까지 진행하면서 2,3,4를 모두 방문 처리하고 반복하지 않기 때문에 2에서 시작한 2,3,4, 3에서 시작한 3,4, 4에서 시작한 4의 경우를 찾지 않고 넘어간다.

 

오랜만에 고민하다가 나름대로 이쁘게 푼 것 같아서 기분이 좋았다.