#6. 해시테이블2 / python set, dictionary

2023.09.29 - #1. 해시테이블 (hash) / python dictionary

#1. 해시테이블 (hash) / python dictionary

이전에 list를 딕셔너리로 변환해서 빠르게 조회하는 방법으로 문제를 풀어보았다.

오늘은 해시테이블로 난이도가 좀 더 있는 문제를 풀어보려고 한다.

 

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

Longest Consecutive Sequence - LeetCode

숫자가 담긴 리스트가 주어지고, 해당 리스트에서 연속된 숫자가 얼마나 되는지 int값을 return하는 문제이다.

 

예시)

input = [1,3,4,5,9]

output = 3

 

직관적으로 생각하면 list를 돌면서 연속된 숫자를 계속 검사하는 방법이 있다. 

그러면 리스트를 1차로 돌면서, 값 하나를 위해 비교할때마다 전체 리스트를 돌아 기본 O(n제곱) 시간이 걸리는데,

거기서 연속된 숫자를 차례대로 또 돌기때문에 최악의 경우 O(N)이 더 걸려 최대 O(N세제곱)까지 걸리게된다.

여기서 시간을 단축할 수 있는 두가지 key point가 있다.

 

1. 연속된 숫자가 있는지 검사할 때 O(1)으로 할 수 있는 방법

지금은 리스트형식으로 조회하기때문에 1 다음 2가 있는지 보려면 리스트를 처음부터 끝까지 돌아야된다.

리스트를 딕셔너리 형태로 바꾸면 1 다음 2가 있는지 O(1)으로 찾고 바로 넘어갈 수 있다.

 

2. 가장 긴 연속된 숫자 찾으면, 그 안에 중복되는 연속된 숫자 검사는 하지 않기

예시에서 3,4,5를 찾았으면 4,5는 또 반복문을 돌면서 검사할 필요가 없다.

이 조건을 주는걸 생각하기가 어려운데 이 조건이 중요하다.

즉 시작하려는 값이 연속된 숫자의 최솟값일때만 연속된 숫자를 조회한다.

3으로 시작하려고 할때 2가 있는지 봤을때 없기때문에 연속된 숫자의 최솟값이다.

4로 시작하려고 할때 3이 있기 때문에 연속된 숫자의 최솟값이 아니다. -> 반복문 돌지말아라

 

3. 추가적으로 작업시간을 줄일 수 있는것들

1) input이 빈 값일 때-> 바로 return 0

2) 만약 리스트에 연속 된 값중에 중복값이 있을경우 1로 치기 때문에 중복 제거 -> dictionary 가 아닌 set으로 만들어주기

set도 해시로 구현되어 있음

중복값이 필요없을 경우 딕셔너리보다 set을 사용하는게 훨씬 빠르다.

예를들어 [1,1,2,3] 리스트가 주어졌을 때 딕셔너리로 그대로 사용하면 0번째 인덱스에서 1,2,3을 검사하고 1번째 인덱스에서 또 1,2,3을 검사하게 된다. set으로 만들어주면 (1,2,3) 이 되기 때문에 같은 조건을 여러번 조회하지 않아서 중복을 줄여준다.

 

코드

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        num_d =  set(nums)
        
        max_cnt = 1 
        for n in num_d:
            if n-1 not in num_d:
                cnt = 1 
                while n+cnt in num_d:
                    cnt += 1 
                if cnt >= max_cnt:
                    max_cnt = cnt 
            
        return max_cnt