✉️문제
https://leetcode.com/problems/longest-consecutive-sequence/description/
Longest Consecutive Sequence - LeetCode
Can you solve this real interview question? 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. Example 1: Input:
leetcode.com
📝 접근
Set 배열에 모든 배열 요소를 집어넣은 다음에 연속적인 수가 있는지 비교한다.
🗝 문제풀이
이번에는 코드의 수정 부분을 기억하기 위해 시도한 접근 방법도 같이 기록해둔다.
[첫 번째 시도 - TLE]
왜 TLE가 나는지 [100, 4, 200, 1, 3, 2] 테스트 케이스를 가지고 생각해보자.
n = 4일 때 while문이 3번 반복된다.
n = 3일 때 while문이 2번 반복된다.
만약 배열의 모든 수가 연속적인 수라면 최악의 경우 O(N^2)이 된다. [1,2,3,4,5,6,7,8,9,10] 을 가지고 직접 해보자 !
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int n : nums) {
set.add(n);
}
int answer = 0;
for(int n : set) {
int length = 1;
if(set.contains(n - 1)) {
while(set.contains(n - 1)) {
length++;
n--;
}
}
answer = Math.max(answer, length);
}
return answer;
}
이를 해결하기 위해 코드를 살짝 변경하였다.
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int n : nums) {
set.add(n);
}
int answer = 0;
for(int n : set) {
int length = 1;
/* 바뀐 부분 시작 */
if(!set.contains(n - 1)) {
while(set.contains(n + length)) {
length++;
}
answer = Math.max(answer, length);
}
/* 바뀐 부분 끝 */
}
return answer;
}