[LeetCode#128] Longest Consecutive Sequence

 

❐ Description

---

문제링크	https://leetcode.com/problems/longest-consecutive-sequence/description/
난이도	medium(골드3~2)

 

 

 

 

 

❐ 문제 분석

---

주어진 배열에서 가장 긴 연속되는 요소의 길이를 구하는 문제이다.

중복되는 숫자는 제외해야 하며, `O(n)`의 시간 복잡도로 구현해야 한다.

 

 

 

 

 

❐ 문제 풀이

---

1. 시간 복잡도 `O(NlogN)`

정렬을 사용해서 풀이할 수 있는 방법이다. 물론 문제의 요구사항인 시간복잡도 보다 크지만,

문제 제약 조건이 허술해서 이 방법으로도 풀이는 된다.

public int longestConsecutive(int[] nums) {
    Arrays.sort(nums);
    int maxLength = -1;

    int cursor = 0;
    int currentLength = 1;
    while (cursor < nums.length - 1) {
        int current = nums[cursor];
        int next = nums[cursor + 1];

        if (Math.abs(next - current) == 1) {
            currentLength++;
            cursor++;
        } else if (current == next) {
            cursor++;
        } else {
            maxLength = Math.max(maxLength, currentLength);
            cursor++;
            currentLength = 1;
        }
    }
    maxLength = Math.max(maxLength, currentLength);
    return maxLength;
}

• 차이의 절대 값이 1인 경우는 `연속된 수`라고 생각할 수 있다.
• 값이 동일한 경우에는 cursor만 오른쪽으로 한 칸 이동한다.

 

 

2. 시간 복잡도 `O(n)`

 

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

    Set<Integer> numsSet = new HashSet<>();
    for (int num : nums) {
        numsSet.add(num);
    }

    int maxLen = 0;
    for (int num : numsSet) {
        if (!numsSet.contains(num - 1)) {
            int currentNum = num;
            int currentLen = 1;

            while (numsSet.contains(currentNum + 1)) {
                currentNum++;
                currentLen++;
            }
            maxLen = Math.max(maxLen, currentLen);
        }

    }
    return maxLen;
}

• HashSet을 이용하는 풀이다.
• 현재 숫자보다 1 작은 값이 set에 존재하지 않는다면, 현재 숫자는 시작점이다.
• 현재 숫자에서 1 씩 더하면서, 그 값이 set에 존재하는지 확인한다.

 

이 문제를 풀면서 HashSet에 대한 의문점이 있었는데 아래 블로그를 보고 의문점을 해소할 수 있었다.

참고 블로그 링크

 

 

 

 

 

---