128: Longest Consecutive Sequence

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

---

1. 문제

• Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
  You must write an algorithm that runs in O(n) time.

 

---

2. 문제의 조건

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

 

---

3. 문제 접근

• 아이디어
  
  저는 처음에 O(N)이란 시간제한을 보고 Counter Sort의 아이디어를 떠올려 list로 해결하려 했습니다.
  min값을 찾고 -가 되는 값을 각 배열에 더해줄 생각을 하였습니다. (-3, 4, -1, 3)이 나올 경우 arr[-3]은 존재하지 않으므로 arr[-3]을 arr[0]으로 보정시켜주기 위해 arr[-3 + min(arr)]로 할생각.
  하지만 입력값을 보니 10^9 .. Counter Sort방식을 사용하기엔 너무 많은 메모리와 리스트를 생성하는 것 자체만으로도 굉장히 많은 시간이 소요된다는걸 깨닫고 고민한 끝에 알고리즘 강의 때 배운 Find-union(Dispoint Set) 방식과 DFS를 생각하였고 DFS로 해결하고자 하였습니다.
  주어진 배열의 최소값을 찾고 해당 최소값부터 +1 씩 한 값을 찾아가며 탐색하는 것입니다.[-3, -2, -1, 3,  5, 7]이 될 경우 최소값은 -3이고 -3 + 1인 -2를 탐색하고 +1 인 -1을 탐색하고 +1 인 0을 찾는데 만약 없으면 이 길이는 3을 반환합니다. 이 때, 3, 5, 7에 대한 탐색이 수행되지 않았으므로 남은 배열중 최소를 찾고 처음과 같이 탐색을 진행합니다.

 

---

4. 풀이 방법

• 인접리스트로 (key, value) 값, 방문상태 로 기억합니다.
• 최소값을 찾고 그 최소값을 기준으로 DFS를 수행합니다  ---- 1
  만약 방문하려는 시점이 존재하지 않거나 이미 방문해 있으면 지금까지 방문한 길이를 return합니다.
  아니라면
  지금 방문한 곳을 True로 만들어주고 start + 1을 탐색합니다. (length도 1 증가해야함)
• 아직 방문되지 않은곳을 파악 후 list로 만들어주고 모든 지점을 방문할 때 까지 무한반복합니다. (memory[data] 가 모두 True이면 전부다 방문한 상태임.)
• 1부터 반복합니다.

 

---

5. 소스코드

• https://cjw-git.tistory.com/180

 

---

 

cjw.git@gmail.com