[1스4코2파] # 175. LeetCode 128. Longest Consecutive Sequence (Array&Hashing)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (175차)
[4코1파] 2023.01.13~ (167일차)
[1스4코1파] 2023.04.12~ (78일차)
[1스4코2파] 2023.05.03 ~ (56일차)

Today :

2023.06.27 [175일차]
LeetCode Patterns
https://leetcode.com/problems/longest-consecutive-sequence/description/

128. Longest Consecutive Sequence

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

문제 설명

int형 원소로 구성된 리스트 nums 에서 연속된 숫자의 길이의 최댓값을 찾는 것.

문제 풀이 방법

영상을 봤는데 어떻게 푸냐면
연속된 원소들을 찾는 방법이기 때문에 시작점인 원소를 먼저 찾는 것을 base로 한다. 시작점 원소로부터 연속된 숫자열의 길이를 찾아서 max 값을 return 하는 것이기 때문임

list를 nums의 집합(set)으로 우선 만들어서 uniuqe 한 원소만 가지고 있고, list를 순회하면서 해당 원소의 바로 앞 숫자가 set에 있으면 length를 늘리고 없을 때까지 while문을 돈다.
순회를 다 하고 length의 max값을 return
그러면 O(N)

내 코드

class Solution:
    def longestConsecutive(self, nums:list) -> int:
        numSet = set(nums)
        longest = 0
        
        for num in nums:
            if num-1 not in numSet:
                length = 0
                while num+length in numSet:
                    length+=1
                    
                longest = max(longest, length)
                
        return longest

증빙

여담

집에가고싶다