LeetCode - Longest Consecutive

문제

💡 정렬되어 있지 않은 정수형 배열 nums가 주어졌다. nums 원소를 가지고 만들 수 있는 가장 긴 연속된 수의 갯수는 몇개인지 반환하시오.

예시

• Input: nums = [100,4,200,1,3,2]
• Output: 4
• 요소들의 가장 긴 연속은 1, 2, 3, 4

제약 조건

• 0 <= nums.length <= 10^5
• 10^9 <= nums[i] <= 10^9

풀이

문제 이해하기

• input은 정수형 배열이다.
• input의 크기는 0보다 크고 10^5보다 작다.
  • input이 0인 경우 발생할 수 있는 오류를 처리해야한다. input이 0일때의 가장 긴 연속은 0이다.
  • input의 최댓값에 따라 N^2 보다 작은 시간복잡도를 가진 알고리즘을 선택해야한다.
• output은 정수다.
• 시간복잡도를 계산한기 위한 N은 input 배열의 길이다.

접근 방법 생각하기

• 리스트를 사용해서 완전탐색으로 풀어보자.
  • 먼저 배열을 순회해야한다. 그리고 배열에서 요소의 연속된 숫자가 있는지 찾아야한다. 만약 연속된 숫자가 존재한다면 다음 숫자가 있는지 찾아봐야한다.
  • 이 방법을 사용하면 시간복잡도가 N^3이된다.
• 자료구조와 알고리즘을 활용하여 시간복잡도를 줄여보자.
  • 리스트 대신 해시 테이블을 사용하면 검색의 시간복잡도가 O(N)에서 O(1)으로 줄어든다.
  • 현재 요소보다 1작은 숫자가 있다면 연속된 숫자를 구해봐야 중복이므로 조건문으로 배제한다.
  • 이 알고리즘을 모두 적용하면 시간복잡도가 O(N)으로 줄어든다.

코드 설계

1. input 배열을 순회하여 Hash Table에 담는다.
2. input 배열을 순회하여 연속된 숫자가 있는지 찾는다.
   1. input의 크기가 0인 경우 0을 반환한다.
   2. 현재 요소보다 1작은 숫자가 없는 경우에만 연속된 숫자를 찾는다.
   3. 요소를 찾을때 Hash Table에서 찾는다.
   4. 요소를 찾으면 연속 카운트를 상승시킨다.
3. 연속 카운트를 반환한다.

코드 구현

public static int getLongestConsecutive(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }

    int result = 1;
    Set<Integer> set = initNumsSet(nums);

    for (int num : nums) {
        int count = getConsecutiveCount(set, num);
        result = Math.max(result, count);
    }

    return result;
}

public static Set<Integer> initNumsSet(int[] nums) {
    Set<Integer> result = new HashSet<>();
    for (int num : nums) {
        result.add(num);
    }
    return result;
}

public static int getConsecutiveCount(Set<Integer> set, int num) {
    int result = 1;
    if (!set.contains(num - 1)) {
        while (set.contains(num + 1)) {
            num++;
            result++;
        }
    }
    return result;
}

@Test
void getLongestConsecutive() {
    int result = LongestConsecutive.getLongestConsecutive(new int[]{100, 4, 200, 1, 3, 2});
    int result2 = LongestConsecutive.getLongestConsecutive(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1});
    int result3 = LongestConsecutive.getLongestConsecutive(new int[]{});
    Assertions.assertEquals(4, result);
    Assertions.assertEquals(9, result2);
    Assertions.assertEquals(0, result3);
}