Longest Consecutive Sequence - LeetCode
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.
정수 배열인 nums 가 주어졌을 때, 가장 긴 연속하는 원소로 이루어진 수열의 길이는?
그리고 O(n) 으로 풀어야 한다.
예를들어 [100,4,200,1,3,2] 에서 1,2,3,4 가 가장 긴 연속하는 수열인거임.
• 0 <= nums.length <= 10^5
- 가장 먼저 떠오르는 생각은 아마 → “정렬" 하면 되잖아??? 이다
- 근데 “정렬" 을 할 경우 → 효율이 가장 좋은 방식으로 풀더라도 O(nlogn) 이라는 것……
- 같은 의미에서 자동 정렬되는 자료구조에 넣는 것도 아무리 효율이 좋아도 O(nlogn) 이다.
그래도 일단 brute force (시간초과)
- 이 때도 주의해야 하는게 있다 → “중복된 값이 존재하는 경우" 다
- 그리고 당연히 시간 초과가 나올 것이다 이거는 O(n^2) 으로 하는 풀이이기 때문이다.
import java.util.*;
class Solution {
public int longestConsecutive(int[] nums) {
// System.out.println("==================");
Arrays.sort(nums);
int max = 0;
for(int i = 0 ; i < nums.length;i++) {
int cnt = 1;
for( int j = i + 1; j < nums.length; j++) {
if(nums[j] == nums[j - 1] + 1) {
// System.out.println("INCREMENT : nums[j] : " + nums[j] + ", nums[j - 1] : "+ nums[j - 1] );
cnt++;
}
else if(nums[j] == nums[j - 1]) {
// System.out.println("SAME : nums[j] : " + nums[j] + ", nums[j - 1] : "+ nums[j - 1] );
continue;
}
else {
// System.out.println("DECRESE : nums[j] : " + nums[j] + ", nums[j - 1] : "+ nums[j - 1] );
i = j-1;
break;
}
}
max = Math.max(max, cnt);
}
return max;
}
}이번에도 못 풀었음 → 재귀로 풀이함
처음에 뭔가 HashMap 같은거를 사용해야 하나 했는데, 보니까 HashSet 을 사용하는 풀이가 있었음
가장 처음에 Set 에다가 모든 원소들을 넣어 둔다. ( 중복도 제거 , 어떤 원소를 O(1) 로 찾을 수 있다- n+-1 이 존재하는지 찾아볼 때 사용 )
Set 을 iterate 하면서, 방금 접근한 그 원소의 앞 or 뒤의 숫자를 가진 원소가 Set 에 존재한다면
- Set 에서 이를 제거
- 그 앞 or 뒤의 숫자를 이제 “현재 숫자" 로 해서 또 다시 Set 에서 찾아봄 + consecutive length 를 증가시킨다.
결과적으로 O(n) 으로 풀이가 가능해진다
( 참고로, Java 의 Iterator 는 iterator 를 사용해 접근하고 있는 원소에 대한 값의 변경은 가능하나, 제거와 같이 Collections 에서 아예 삭제 하는 경우 런타임 예외가 발생한다.
따라서 Set 을 직접 도는게 아니라, 주어진 배열을 iterate 하면서 해당 원소가 현재 set 에 존재하는지를 확인 해 봐야 한다 )
import java.io.IOException;
import java.util.HashSet;
import java.util.Set;
public class Main {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i : nums ) {
set.add(i);
}
return findMax(set, nums);
}
// iterator 는 사용하면 안되고 -> 그냥 arr 을 좀 사용해보자
private int findMax(Set<Integer> set , int[] arr) {
int max = 0;
for(int n : arr) {
int cnt = 0;
// 포함하고 있다면
while(set.contains(n)){
cnt++;
set.remove(n);
cnt += findLeft(set, n);
cnt += findRight(set, n);
}
max = Math.max(max, cnt);
}
return max;
}
private int findLeft(Set<Integer> set, int n) {
if(set.contains(n-1)) {
set.remove(n-1);
return findLeft(set, n-1) + 1;
}
else return 0;
}
private int findRight(Set<Integer> set, int n) {
if(set.contains(n+1)) {
set.remove(n+1);
return findRight(set, n+1) + 1;
}
else return 0;
}
public static void main(String[] args) throws IOException {
Main main = new Main();
// int res = main.longestConsecutive(new int[]{9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6});
int res = main.longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1});
System.out.println(res);
}
}재귀가 아니게 풀수도 있다
import java.util.*;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i : nums ) {
set.add(i);
}
return findMax(set, nums);
}
// iterator 는 사용하면 안되고 -> 그냥 arr 을 좀 사용해보자
private int findMax(Set<Integer> set , int[] arr) {
int max = 0;
for(int n : arr) {
int cnt = 0;
// 포함하고 있다면
if(set.contains(n)){
cnt++;
set.remove(n);
int left = n - 1;
int right = n + 1;
while(set.contains(left)) {
set.remove(left);
cnt++;
left--;
}
while(set.contains(right)) {
set.remove(right);
cnt++;
right++;
}
}
max = Math.max(max, cnt);
}
return max;
}
}