딕션어리 문제 2 - Longest Consecutive Sequence

해시테이블 코테 적용 방법

• 메모리를 활용해서 시간복잡도를 줄이자!
• key in  { } 가 핵심!

문제

해석

[100, 4, 200, 1, 3, 2]

이 숫자들을 사용해서 연속된 수를 만들어야한다. 연속된 수를 만들 수 있는 경우의 수는 [1, 2, 3, 4] 이다 [1, 2, 3, 4]가 가장 길기 때문에 4를 리턴해야한다.

 

[0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

두번째 예시에서 문제는 0이 두번 있다는 것이다. 하지만 연속된 수를 찾을 때는 0이 한번만 들어가기 때문에 조심해야한다

제약 조건

nums가 커지면 커질수록 시간복잡도가 높아진다. 여기선 10^5승까지로 되어있는데 O(n^2)인 시간복잡도로는 시간 초과가 난다.

즉 완전 탐색같은 알고리즘은 쓸 수 없다. 

또한 0일 수도 있는데 이 말은 nums 배열에 아무 원소도 가지고 있지 않을 수 있다. 

 

nums안의 원소는 -10^9 ~ 10^9 까지이다 즉 int 자료형으로 충분히 쓸 수 있다는 것이다. 자바로 풀때는 주의하자

접근

1. 주어진 nums의 길이만큼 반복
2. 중복제거 조건
3. 다음 숫자기 있다면 계속 반복(while)

코드 및 해석

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        longest = 0
        num_dict = {}
        
        # 딕션어리에 주어진 nums다 넣기
        # 이때 key 값은 nums, value 값은 True로 통일함
        for num in nums:
            num_dict[num] = True
            
        # num_dict 이라는 딕션어리에 있는 요소들을 num이라는 변수에 담아서 하나씩 순회한다
        for num in num_dict:
          
            # 현재 {6: T, 7: T, 100: T , 5: T, 4: T, 4: T} 이런식으로 담아져 있는데
            # 6이 가장 작은 숫자인지 확인해야한다
            # 6-1이 없다면, 즉 가장 작은 숫자라면 조건문을 실행하지만 아니라면 이 조건에 맞는 숫자까지 조건문에 들어가지 않고 계속 순회함
            if num - 1 not in num_dict:
              # 100을 검사할때 99가 없기 때문에 조건문으로 들어왔음
              # 이제 101, 102, 103, 처럼 연속된 숫자가 있는지 하나하나 확인 하는 과정
              
                # cnt = 1 인이유는 어쨌든 연속된 숫자가 나 혼자(나 자신)이라도 있기 때문에 이렇게 설정
                cnt = 1
                # target을 101로 설정
                target = num + 1
                
                # target이 있다면 반복함
                # num_dict 만약 이렇게 딕션어리가 아니라 일반 리스트였으면 O(n)의 시간 복잡도가 걸리니 주의
                # 만약 target이 없다면 이 조건문 나가게 된다
                while target in num_dict:
                    target += 1
                    cnt += 1
                
                # while 조건문을 나가게 되면 여기로 옴
                # longest와 cnt 중에 더 큰수를 저장한다.
                longest = max(longest, cnt)
        return longest