[LeetCode] 128. Longest Consecutive Sequence (Java)

문제

 

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

Longest Consecutive Sequence - LeetCode

 

풀이

 

난이도: Medium 

 

간단히 정렬로 해결하고 싶지만 시작 복잡도를 O(n)으로 구현해야 하는 문제.

O(n)으로 구현하기 위해서는 값의 삽입, 삭제가 O(1)에 가능한 자료구조를 사용해야 한다.

가장 간단한 1차원 배열에 nums의 원소들을 저장하는 것은 nums[i]의 범위 때문에 불가능하다.

• -10^9 <= nums[i] <= 10^9

하지만 다행히도 삽입 삭제의 시간 복잡도가 O(1)인 자료구조가 있었으니,

바로 key를 Hashig을 통해 저장하는 HashMap이다.

 

이를 가능하게 하는 내부 구조에 대해 궁금하다면 다음 게시글을 참조하자.

사바라다는 차곡차곡님의 [자료구조] 코드로 알아보는 java의 Hashmap

 

삽입 삭제가 O(1)에 가능하면 값을 찾는 것 또한 O(1)에 가능하다.

따라서 nums[i]의 value에 해당하는 노드들을 만들고 value -1, value + 1에 해당하는 node가 생성되면 map에서 찾아 서로를 이어 주자.

 

class Node{
    int num;
    Node left=null, right = null;
    boolean visited = false;
    Node(int num){
        this.num = num;
    }
}

그래프의 생성이 끝났다면 방문 여부를 나타내는 visited를 이용하여 왼쪽(value -1)과 오른쪽(value+1)에 이어진 모든 노드의 개수를 세어주면 연속되는 값의 길이를 찾을 수 있다.

 

 

코드

 

 

Node를 map의 value로 저장하지 않고 자신의 그룹의 길이를 value에 저장하는 더 깔끔한 방법도 있다.

이때 핵심이 되는 것이 연속되는 그룹의 모든 value를 바꾸어주면 O(n)의 복잡도가 아니게 된다.

사실, 연속되는 그룹의 양 끝 값에서만 그룹이 결합되므로 그룹의 결합 시에 양끝의 value만 새로운 그룹의 길이로 업데이트해주면 된다.

 

출처: My really simple Java O(n) solution - Accepted