[LeetCode] 128. Longest Consecutive Sequence - Java

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

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.

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

풀이

풀이 과정

정렬되지 않은 정수 배열이 주어졌을 때 가장 긴 연속된 요소들의 길이를 구하는 문제이다.

Set에 nums 배열의 모든 요소들을 넣어 중복을 제거한 뒤 nums 배열의 모든 요소를 탐색하며 연속된 값이 Set에 존재하는지 여부를 판단하며 길이를 구하는 방향으로 풀이한다.

우선 탐색에 사용할 Set을 선언하고 nums 배열의 모든 요소들을 넣어준다.

// 탐색에 사용할 set
Set<Integer> set = new HashSet<>();
// nums 배열의 모든 값을 set에 저장
for(int i : nums) set.add(i);
// Longest Consecutive Sequence

 

최종적으로 반환할 결과값 변수를 하나 선언하고 nums 배열의 모든 값에 대해 탐색을 시작한다.

// Longest Consecutive Sequence
int lcs = 0;

1. 현재 탐색중인 숫자에 대해 연속하는 감소하는 숫자와 증가하는 숫자 양쪽을 모두 비교하며 Set에서 제거하는 방법을 사용할 수도 있고
2. 현재 탐색중인 숫자가 연속하는 숫자의 시작인 경우에만 길이를 탐색하는 방법을 사용할 수도 있다.

1번 방법의 경우에는 다음과 같고

// nums 배열의 모든 값에 대해 탐색
for(int i : nums) {
    // 연속하는 수의 길이
    int length = 1;
    // Set에서 현재 탐색중인 값 제거
    set.remove(i);
    // 연속하는 감소하는 수
    int left = i - 1;
    // 연속하는 증가하는 수
    int right = i + 1;

    // 연속하는 감소하는 수 탐색
    while(set.contains(left)) {
        // 길이 증가
        length++;
        // 탐색하는 수 감소
        left--;
    }

    // 연속하는 증가하는 수 탐색
    while(set.contains(right)) {
        // 길이 증가
        length++;
        // 탐색하는 수 감소
        right++;
    }
    // 최대값 갱신
    lcs = Math.max(lcs, length);
}

2번 같은 경우에는 다음과 같이 풀이할 수 있다.

// nums 배열의 모든 값에 대해 탐색
for(int i : nums) {
    // i가 연속된 숫자의 시작인 경우에만 길이 탐색
    if(!set.contains(i - 1)) {
        int length = 1;
        // 연속된 증가하는 숫자들에 대해 탐색
        while(set.contains(i + 1)) {
            length++;   // 길이 증가
            i++;        // 현재 탐색 값 증가
        }

        // 최대값 갱신
        lcs = Math.max(lcs, length);
    }
}

---

최종 코드

class Solution {
    public int longestConsecutive(int[] nums) {
        // 탐색에 사용할 set
        Set<Integer> set = new HashSet<>();
        // nums 배열의 모든 값을 set에 저장
        for(int i : nums) set.add(i);
        // Longest Consecutive Sequence
        int lcs = 0;
        // nums 배열의 모든 값에 대해 탐색
        for(int i : nums) {
            // 연속하는 수의 길이
            int length = 1;
            // Set에서 현재 탐색중인 값 제거
            set.remove(i);
            // 연속하는 감소하는 수
            int left = i - 1;
            // 연속하는 증가하는 수
            int right = i + 1;

            // 연속하는 감소하는 수 탐색
            while(set.contains(left)) {
                // 길이 증가
                length++;
                // 탐색하는 수 감소
                left--;
            }
            
            // 연속하는 증가하는 수 탐색
            while(set.contains(right)) {
                // 길이 증가
                length++;
                // 탐색하는 수 감소
                right++;
            }
            // 최대값 갱신
            lcs = Math.max(lcs, length);
        }

        return lcs;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        // 탐색에 사용할 set
        Set<Integer> set = new HashSet<>();
        // nums 배열의 모든 값을 set에 저장
        for(int i : nums) set.add(i);
        // Longest Consecutive Sequence
        int lcs = 0;
        // nums 배열의 모든 값에 대해 탐색
        for(int i : nums) {
            // i가 연속된 숫자의 시작인 경우에만 길이 탐색
            if(!set.contains(i - 1)) {
                int length = 1;
                // 연속된 증가하는 숫자들에 대해 탐색
                while(set.contains(i + 1)) {
                    length++;   // 길이 증가
                    i++;        // 현재 탐색 값 증가
                }
                
                // 최대값 갱신
                lcs = Math.max(lcs, length);
            }
        }

        return lcs;
    }
}

---