Blind 75 | Longest Consecutive Sequence (Array 7 / 8)

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

Longest Consecutive Sequence - LeetCode

 

Longest Consecutive Sequence - 가장 길게 연속되는 숫자

 

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.

 

정렬이 안된 정수 배열이 주어졌을 때, 가장 길게 연속되는 숫자들의 길이를 구하라.

알고리즘은 O(n)이어야 한다.

 

 

개요

 

언제나 정렬이 안된 정수 배열이 주어진다하면 본능적으로 정렬을 하면 되잖아? 라고 생각하게 된다.

 

이 문제와 같은 경우 변수 length를 정의해놓고 정수 배열을 Set으로 만든 후 정렬 => for 문을 돌리면서

 

다음 숫자가 현재 숫자보다 1이 크다면 length를 1씩 늘려가면 간단히 해결되는 문제다.

 

그러나 알고리즘은 O(n)이어야한다는 조건이 걸렸고 정렬은 O(nlogn)이기에 다른 방법을 사용해야 한다. 

 

이 경우 Set의 메서드와 연속된 숫자가 시작하는 시작점을 찾으면 풀 수 있다.

 

 

풀이 방법

 

정수 배열을 Set으로 만들면 일단 중복이 사라진다.

 

예제 1을 보면 [100,4,200,1,3,2] 이 주어진다.

 

이 배열을 Set으로 변환하면 Set(6) {100, 4, 200, 1, 3, 2}가 된다. 중복이 없기에 값은 동일하다.

 

여기서 연속된 숫자의 시작점인 1을 찾으려면 어떻게 해야할까? 

 

정렬은 할 수 없다. 1보다 큰 숫자를 찾아봐야 2, 3, 4, 100, 200이 해당되고 

 

1보다 작은 숫자를 찾는다 그래도 이 예제에는 없는 -4, -3, -2 이런 가능성도 생각해야한다.

 

정답은 1보다 1 작은 숫자인 0이 있는지를 찾는다.

 

만약 1보다 1 작은 숫자가 없다면 1은 연속되는 숫자의 시작이다.

 

 

풀이

 

배열을 세트로 전환 한 후 

 

for 문에서 현재의 num 보다 1 작은 숫자가 있다면 다음 num을 본다.

 

만약 없다면 현재 num은 연속되는 숫자의 시작점인데

 

지금 num보다 1보다 큰 숫자가 있다면 계속해서 1을 더하면서

 

streak를 구한다.

 

연속이 끝나면 max를 업데이트해주고 streak는 다시 1로 초기화해준다.

 

그리고 마지막에 max를 리턴하면 푼다.

 

 

정답이나 원리를 알면 굉장히 쉽고 기발하지만 막상 이 풀이를

 

처음부터 생각해내려하면 힘들다.

 

나도 처음 이 문제를 풀 때 30분 정도 끙끙댔지만 생각 해 낼 수 없었다.