LeetCode 128(Longest Consecutive Sequence, Python)

1. 문제 링크 

• https://leetcode.com/problems/longest-consecutive-sequence/

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• unsorted 된 정수로 구성된 nums가 주어졌을 때, 가장 긴 연속된 elements 순서의 길이를 반환 
• 시간복잡도는 O(n)으로 작성할 것
• 예시1) 
  • nums = [100,4,200,1,3,2]일 때, 
    • 여기서 가장 긴 연속된 시퀀스는 [1,2,3,4]이기 때문에, 해당하는 길이인 4를 반환
• 예시2)
  • nums = [0,3,7,2,5,8,4,6,0,1]일 때,
    • 가장 연속된 시퀀스는 [0,1,2,3,4,5,6,7,8]로 9를 반환
    • 해당 예시에서 같은 정수가 반복해서 등장할 수 있음을 알 수 있음 

 

3. 처음 풀이

• element에 같은 정수가 반복될 수 있으므로, 집합 변환 후 다시 array화 하여 중복을 없앤 뒤, 
• nums를 sort를 시켰다.
  • 만약 i번째 element의 값과 i+1번째 element의 값이 1 차이가 난다면, 연속된 sequence이므로, output에 1을 더하였고, 
  • 만약 i가 nums array의 끝에 도달했거나, 혹은 i+1과의 차이가 1이 아니라면, 
    • 지금까지의 output과, 이전의 max length를 비교하여, output이 max_length보다 크면, 해당값으로 max_length를 업데이트하고,
    • output을 1로 리셋하였다. 
  • 최종적으로 max_length를 반환하였다.
  • 그런데.. sort의 경우 시간복잡도가 O(NlogN)이다. 그래서 문제의 조건에 부합하지 않았다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:

        nums = list(set(nums))
        nums.sort()
        output = 1
        max_length = 0

        for i in range(len(nums)):
            if (i == len(nums)-1) or (nums[i+1]-nums[i] != 1):
                if output > max_length:
                    max_length = output
                output = 1
            else:
                output +=1
        
        return max_length

 

4. 다른 풀이

• sort를 사용하지 않고 푼 풀이 
• nums를 set으로 변환하여 중복을 없애둔 다음에
  • nums 안에 있는 element를 for문을 돌리면서,
    • 만약 element n에 대하여 n-1이 집합에 없다면, n이 연속된 sequence의 시작점이므로 
      • length를 1로 초기화하고,
      • n+length가 num에 존재할 때까지 while문을 돌린 후,
      • 이전에 저장되있던 longest 변수와 비교하여 max값으로 업데이트한다.
    • 예를 들어, 예시의 [100,4,200,1,3,2]의 경우, 
      • n=100일 때, 100-1인 99는 해당 리스트에 존재하지 않기 때문에, length =1이 되고, 100+1은 존재하지 않기 때문에, longest가 1로 저장이 된다.
      • n=4일 때는, 4-1인 3이 list에 존재하므로 pass하고,
      • n=200일 때는, 100과 동일하게 length=1이 되어, longest는 max(1,1)로 그대로 1이 된다.
      • n=1일 때는, 1-1인 0이 리스트에 존재하지 않아서, length =1로 초기화되고, 2,3,4가 차례로 nums에 존재하기 때문에, length는 4가 되고, longest도 4로 바뀌어 저장이 된다.
      • 마찬가지로, n=3,n=2일 때는 각각 n=2,n=1이 nums에 존재하므로 pass되어,
      • 최종 길이 4가 반환된다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        num_set = set(nums)

        for n in num_set:
            if (n-1) not in num_set:
                length = 1
                while (n+length) in num_set:
                    length += 1
                longest = max(longest, length)
        
        return longest

 

5. 배운 점

• sort는 시간복잡도가 O(nlogn)이다.
• sort를 사용하지 않고 푸는 풀이