Today I Learned

오늘도 코테 연습!

Longest Consecutive Sequence

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

문제

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.

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.

풀이 과정

• 문제는 정수 배열에서 가장 긴 연속적인 숫자 시퀀스의 길이를 찾는 것인데, 중요한 것은 시간복잡도 O(n)을 지켜야 되는 것이다.

1. 먼저 주어진 배열을 HashSet에 저장한다. HashSet에선 중복된 요소를 허용하지 않으므로 중복된 숫자는 하나만 저장된다.

2. 배열을 반복하면서 각 숫자에 대해 연속적인 시퀀스의 길이를 계산한다.

3. 각 숫자에 대해 현재 숫자보다 1 작은 숫자가 HashSet에 없는지 확인한다. 없으면 해당 숫자를 시작으로 연속적인 시퀀스를 찾아나간다.

4. 연속적인 시퀀스를 찾을 때마다 현재 시퀀스의 길이를 업데이트하고, 가장 긴 시퀀스의 길이를 저장한다.

5. 모든 숫자에 대해 위 과정을 반복하고, 최종적으로 가장 긴 시퀀스의 길이를 반환하면 배열을 한번 반복하고 각 숫자에 대해 O(1)로 해쉬셋에서 소모하므로 전체 시간복잡도를 O(n)으로 해결할 수 있게 된다.

Java 코드

class Solution {
  public int longestConsecutive(int[] nums) {
    if (nums == null || nums.length == 0)
      return 0;

    HashSet<Integer> set = new HashSet<>();
    for (int num : nums)
      set.add(num);

    int l = 0;

    for (int num : nums) {
      if (!set.contains(num - 1)) {
        int currentNum = num;
        int currentStreak = 1;

        while (set.contains(currentNum + 1)) {
          currentNum++;
          currentStreak++;
        }

        l = Math.max(l, currentStreak);
      }
    }

    return l;
  }
}