Longest Consecutive Sequence

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

문제 파악 [필수 작성]

문제이해

리스트 내 원소로 만들 수 있는 가장 긴 원소배열을 출력

제한 조건 확인

길이 최대 10^5 -> 무조건 O(n) 내에 풀어라

아이디어

연속하다는것은 무엇을 의미?
서로 뺐을때 절대값이 1이 나오는 경우임

nums 내 인덱스의 방문여부를 set 에 저장
nums의 인덱스를 0부터 n-1 까지 탐색
특정인덱스 방문안했을때 특정인덱스 k 가 있을때
딕셔너리에 k+1 이나 k-1 이 있는지 조사
있으면, 해당 방향으로 확장 안될때까지 확장, 확장한 후 해당 인덱스 방문여부 set 에 기록
반대방향으로도 확장 안될때까지 확장, 확장한 후 해당 인덱스 방문여부 set 에 기록
확장한거 길이 max_len 에 업데이트

시간복잡도

n(idx,num 페어 딕트 생성)+n(원소탐색) -> O(n) -> 각 원소 최대 1번만 탐색함

자료구조

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

1차 아이디어(30분 소요)

from collections import defaultdict
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        num_dict = defaultdict(list)

        for idx,num in enumerate(nums):
            num_dict[num].append(idx)

        idx_visited = set()

        for idx in range(len(nums)):
            tmp_len = 0
            if idx not in idx_visited:
                tmp_len += 1
                #print(nums[idx])
                idx_visited.add(idx)
                x_up = nums[idx]
                x_down = nums[idx]
                while x_up+1 in num_dict:
                    x_up += 1
                    tmp_len += 1
                    #print(x_up)
                    for tmp_idx in num_dict[x_up]:
                        idx_visited.add(tmp_idx)
                while x_down-1 in num_dict:
                    x_down -= 1
                    tmp_len += 1
                    #print(x_down)
                    for tmp_idx in num_dict[x_down]:
                        idx_visited.add(tmp_idx)
                max_len = max(max_len,tmp_len)
        #print(idx_visited)
        return max_len

1차 코드 개선

from collections import defaultdict
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        num_dict = defaultdict(list)

        for idx,num in enumerate(nums):
            num_dict[num].append(idx)

        idx_visited = set()

        for idx in range(len(nums)):
            tmp_len = 0
            if idx not in idx_visited:
                tmp_len += 1
                #print(nums[idx])
                idx_visited.add(idx)
                x_up = nums[idx]
                x_down = nums[idx]
                while x_up+1 in num_dict and num_dict[x_up+1][0] not in idx_visited:
                    x_up += 1
                    tmp_len += 1
                    #print(x_up)
                    for tmp_idx in num_dict[x_up]:
                        idx_visited.add(tmp_idx)
                while x_down-1 in num_dict and num_dict[x_down-1][0] not in idx_visited :
                    x_down -= 1
                    tmp_len += 1
                    #print(x_down)
                    for tmp_idx in num_dict[x_down]:
                        idx_visited.add(tmp_idx)
                max_len = max(max_len,tmp_len)
        #print(idx_visited)
        return max_len

1차 코드 재개선

from collections import defaultdict
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        num_dict = defaultdict(list)

        nums_set = set(nums)
        visited_num = set()

        for num in nums:
            tmp_len = 0
            if num not in visited_num:
                visited_num.add(num)
                tmp_len += 1
                
                x_up = num
                while x_up+1 in nums_set and x_up+1 not in visited_num:
                    x_up += 1
                    visited_num.add(x_up)
                    tmp_len += 1
                
                x_down = num
                while x_down-1 in nums_set and x_down-1 not in visited_num:
                    x_down -= 1
                    visited_num.add(x_down)
                    tmp_len += 1

                max_len = max(max_len,tmp_len)

        return max_len

배우게 된 점 [필수 작성]

해설코드

해설코드는 양쪽으로 탐색하지 않고 특정 원소보다 1 작은 원소가 있으면 루프를 돌지 않고, 시작점이 되는 원소를 만났을때만 루프를 돌려줬다. 연산시간 관점에서는 내 코드와 동일할 것으로 보인다. 실제로도 완전히 동일하다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
				#✅ 각 숫자를 key값으로 하여 헤시셋을 만든다.
        num_set = set(nums)
        #✅ 해시셋을 순회한다.
        for num in num_set:
						#✅ 만약 이전 숫자가 존재하지 않는다면, 개수를 1로 초기화한다.
            if num - 1 not in num_set:
                cnt = 1
                target = num + 1
								#✅ 다음 숫자가 존재할 때까지 개수를 1씩 증가시킨다.
								#✅ 연속된 숫자 개수 최댓값을 업데이트한다.
                while target in num_set:
                    target += 1
                    cnt += 1
                longest = max(longest, cnt)
        return longest

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.